3 ms·

> The fact that an n-qubit quantum computing system is significantly powerful than classical system because of 2^n states. But, a classical system with n-bits w

> The fact that an n-qubit quantum computing system is significantly powerful than classical system because of 2^n states. But, a classical system with n-bits will also have 2^n states, isn't it? Let's consider the execution of an algorithm. In the classical case you start with _one_ of 2^n states and keep evolving that single state. In the case of a quantum computer you can start with a superposition of all of the 2^n states and evolve them simultaneously. This is called quantum parallelism. This sounds very powerful but comes with a caveat: at the end of the algorithm you will end up with some other superposition of the 2^n states but you can only read one of them. Which one it is going to be will be decided by the square of the complex amplitudes associated with those states. The greater the squared amplitude, the more likely it is that you will end up measuring the state associated with it. A key requirement when a quantum algorithm is designed is that it should yield a useful state at the time of measurement with high probability. This is in general difficult to do.

nightcracker 6y ago
> In the case of a quantum computer you can start with a superposition of all of the 2^n states and evolve them simultaneously. This is called quantum parallelism. This is a common misrepresentation of how quantum computers work. Because we can start in one state (e.g. |0^n>, the all-zero n-qubit state), and apply the Hadamard gate to each qubit. And now we are in the universal superposition state (measuring has an equal probability for each n-bit bitstring). Oh no! what happened? If you are under the belief that quantum computation is 'like classical computation, but in parallel', going from one single state to a superposition is impossible. In other words, it doesn't accurately capture what quantum computation does.
- attilakun 6y ago
  Granted, it's an oversimplification but I wouldn't call it a misrepresentation. It's one of the (arguably key) things that make quantum algorithms work. To quote Nielsen & Chuang (section 1.4.2 on page 30): > Quantum parallelism is a fundamental feature of many quantum algorithms. Heuristically, and at the risk of over-simplifying, quantum parallelism allows quantum computers to evaluate a function f(x) for many different values of x simultaneously. In this section we explain how quantum parallelism works, and some of its limitations. Then they go on and explain how e.g. the Deutsch–Jozsa algorithm is a good example of this. But I think it's a key component in Shor's algorithm as well when it comes to the period-finding step.

nightcracker 6y ago

> In the case of a quantum computer you can start with a superposition of all of the 2^n states and evolve them simultaneously. This is called quantum parallelism. This is a common misrepresentation of how quantum computers work. Because we can start in one state (e.g. |0^n>, the all-zero n-qubit state), and apply the Hadamard gate to each qubit. And now we are in the universal superposition state (measuring has an equal probability for each n-bit bitstring). Oh no! what happened? If you are under the belief that quantum computation is 'like classical computation, but in parallel', going from one single state to a superposition is impossible. In other words, it doesn't accurately capture what quantum computation does.

attilakun 6y ago
Granted, it's an oversimplification but I wouldn't call it a misrepresentation. It's one of the (arguably key) things that make quantum algorithms work. To quote Nielsen & Chuang (section 1.4.2 on page 30): > Quantum parallelism is a fundamental feature of many quantum algorithms. Heuristically, and at the risk of over-simplifying, quantum parallelism allows quantum computers to evaluate a function f(x) for many different values of x simultaneously. In this section we explain how quantum parallelism works, and some of its limitations. Then they go on and explain how e.g. the Deutsch–Jozsa algorithm is a good example of this. But I think it's a key component in Shor's algorithm as well when it comes to the period-finding step.