# What makes a Quantum Computer Faster for solving specific problems?

I have an undergraduate understanding of Quantum Mechanics (or at least of whatever is covered in Griffith's) and the idea of a Quantum Computer sounds really interesting but I am having some trouble seeing where its effectiveness comes from.

I understand that a qubit, or collection of qubits, can exist in a superposition of states and that you can apply a quantum logic gate to the state of the system to preform computations, for example the Hadamard Gate shown here: https://en.wikipedia.org/wiki/Quantum_logic_gate

What isn't clear is that after applying the gate, your system is still in general in a superposition of states and when you go to make a measurement of the system, it will collapse into one of its eigenstates with probability dependent on the inner product between the current state and the eigenstate. And so you are left with a single result. Can't this same single result be achieved by a series of similar computations on a classical computer with its bits in some determinate configuration? Why do the qubits being in a superposition of states somehow lead to computations being faster?

In order to get a for sure (or at least fairly accurate result) for some series of computations on a set of qubits that were initially in a superposition state, it seems like you would need to repeat the same calculations on the same state multiple times and find the correct distribution of results. So it seems like you would need to repeat the calculation multiple times on a quantum computer where as on a classical computer you only need to do the computation once which begs the question of how is in what respect is the quantum computer faster (assuming the speed of the calculations on both classical and quantum computers are the same or at least similar).

My bad if this is a repost or something.

In some sense your intuition is right, that any that can be done on a quantum computer can also be done on a classical computer. However, simulating the behavior of a quantum computer on a classical computer is very inefficient. In classical computing, the state of $$N$$ bits is represented by $$N$$ binary numbers. However in quantum computing, the state of $$N$$ qubits is represented by $$2^N$$ complex numbers (each qubit can be in one of 2 states, so there are $$2^N$$ possible states, and you need one complex number for every possible state). Therefore it is hopeless to simulate the behavior of a quantum computer with a large number of qubits with on a classical computer. One way to express the mysteriousness of quantum mechanics, is that Nature is able to deal with this exponential number of states efficiently.