Is this algorithm for simulating a quantum computer accurate?

Question

I'm very new to quantum mechanics. I'm thinking of writing a quantum computer simulator, would the following work?

• Each qubit is stored as a single bit,
• For each operation, the qubits involved are transformed into a complex vector of amplitudes of size 2^N. This will result in a vector containing 2^N-1 0s and one 1.
• This vector is multiplied by the unitary matrix representing the operation.
• The resulting vector is squared element-wise.
• An outcome is picked using the elements of the result as probabilities and the qubits are set according to this outcome.

I'm not concerned with the running time or the memory cost of the algorithm. What I am concerned about is whether this would result in a physically accurate simulation.

Answer 1

Yes, this will essentially work, although there are some pitfalls in the way you've phrased things. For one, you cannot store each qubit as a single bit, but you can work things out so that any computation you do starts from a state which can be represented by $N$ classical bits, i.e. the zero state.

Following this your second and third bullet points are correct.

As for the fourth, element-wise squaring implies that your measurement is in the computational basis. If you need to measure in, say, the Fourier basis, you will need to convert to a computational basis measurement by including a Fourier transformation in step 3.

Bullet 5, like bullet 1, conflates the classical information encoded onto/extracted from qubits with the qubits themselves. Everything here is fine assuming you mean for step 5 to be the absolute end of the computation, but you cannot, in general, loop from step 5 back to step 2.

Ultimately the reason your simulation works is that any computation on $N$ qubits can be represented as a single ($2^N\times 2^N$) unitary acting on the zero state followed by measurement in the computational basis. You cannot, however, use a simulation such as yours to do gate-by-gate simulation of a quantum algorithm.

Answer 2

No, this won't work. The last step of picking an outcome by squaring the elements of the result and resetting the qubits are set according to this outcome is equivalent to measuring the state of your quantum compute. If you measure the state of your quantum computer after every step, this decoheres any coherent superposition. You will get a computation which can easily be simulated on a classical computer, and which you won't be able to use for any interesting quantum computations. Pretty much any quantum algorithm that takes more than one step will give an example of a case where this won't give the right answer.

Answer 3

The information about an $N$-qubit computer is given by $2^N$ complex numbers. A single operation means to multiply this vector by a unitary matrix which means doing something between $2^N$ and $4^N$ operations (usually the first one because the operations are "localized" on the qubits, so they're not quite generic matrices of the same size).

At the end, you measure the qubits as $N$ ordinary bits. That's when the vector gets reduced to $2^{N}-1$ zeros and $1$ entry equal to one. It's not quite clear from your wording whether you realize that this special form only occurs once, at the very end of the calculation - after you do the "measurement".

The problem in turning this to a practical solution is that $2^N$ operations is a very high number for useful quantum computers that would have at least $N=128$ or much more. A quantum computer would do the operation in one step instead of $10^{38}$ steps. Also, it wouldn't need the classical memory $10^{38+}$ - just 128 spins etc. - to remember all those quantum amplitudes haha.