Return to Answer

Intuitively speaking, the reason you'd expect quantum computers to take so much space classically is that a quantum state is a weighting of each possible classical state. With $n$ bits you have $2^n$ possible classical states, so you need $2^n$ weighting factors to represent the state of $n$ qubits... unless you find a way to be clever about it.

One way you can be clever is knowing that you're only dealing with simple subset of states. For example, if you know you're dealing with non-entangled states, then you can factor things into $n$ complex weights. More commonly, your quantum state may be the output of a stabilizer circuit, and thus efficiently computable classically.

Another way you can be clever is by working through the weights incrementally, so you don't have to store them all at the same time. This takes a lot longer, though. Basically you can lay out the full sequence of matrix multiplications, then iterate through all the paths that can be multiplied together to contribute to one of the weights. Once you have that final weight, flip an appropriately weighted coin over whether to return it or to go to the next weight.

That's right, despite intuitively involving exponentially more values, BQPSpace is equal to PSPace.

Intuitively speaking, the reason you'd expect quantum computers to take so much space classically is that a quantum state is a weighting of each possible classical state. With $n$ bits you have $2^n$ possible classical states, so you need $2^n$ weighting factors to represent the state of $n$ qubits... unless you find a way to be clever about it.

One way you can be clever is knowing that you're only dealing with a simple subset of the possible quantum states. For example, if you know you're dealing with non-entangled states, then you can factor things into $n$ complex weights. More commonly, your quantum state may be the output of a stabilizer circuit, and thus efficiently computable classically.

Another way you can be clever is by working through the weights incrementally, so you don't have to store them all at the same time. This takes a lot longer, though. Basically you can lay out the full sequence of matrix multiplications, then iterate through all the paths that can be multiplied together to contribute to one of the weights. Once you have that final weight, flip an appropriately weighted coin over whether to return it or to go to the next weight.

That's right, despite intuitively involving exponentially more values, BQPSpace is equal to PSPace.

This question is a bit more complicated than you might expect, because the number of bits you need depends on whether or not you care about how long the computation takes.

If you're willing to wait an amount of time that's exponentially longer than the quantum computer would take, then you can simulate a quantum computer with a classical computer without using exponentially more space. Sacrificing time makes the space overhead polynomial; BQPSpace is equal to PSPace.

(I think the trick is to represent the quantum computation as a chain of matrix multiplications. Instead of computing the intermediate matrices or states, which would take too much space, you slowly but surely iterate over all the ways each path through the matrices can contribute to the probability of a final state and return the state with that probability.)

Intuitively speaking, the reason you'd expect quantum computers to take so much space classically is that a quantum state is a weighting of each possible classical state. With $n$ bits you have $2^n$ classical states, so you need $2^n$ weighting factors to represent the state of $n$ qubits... unless you find a way to be clever about it.

Intuitively speaking, the reason you'd expect quantum computers to take so much space classically is that a quantum state is a weighting of each possible classical state. With $n$ bits you have $2^n$ possible classical states, so you need $2^n$ weighting factors to represent the state of $n$ qubits... unless you find a way to be clever about it.

One way you can be clever is knowing that you're only dealing with simple subset of states. For example, if you know you're dealing with non-entangled states, then you can factor things into $n$ complex weights. More commonly, your quantum state may be the output of a stabilizer circuit, and thus efficiently computable classically.

Another way you can be clever is by working through the weights incrementally, so you don't have to store them all at the same time. This takes a lot longer, though. Basically you can lay out the full sequence of matrix multiplications, then iterate through all the paths that can be multiplied together to contribute to one of the weights. Once you have that final weight, flip an appropriately weighted coin over whether to return it or to go to the next weight.

That's right, despite intuitively involving exponentially more values, BQPSpace is equal to PSPace.

This question is a bit more complicated than you might expect, because the number of bits you need depends on whether or not you care about how long the computation takes.

If you're willing to wait an amount of time that's exponentially longer than the quantum computer would take, then you can simulate a quantum computer with a classical computer that has basically the same number of classical bits as the quantum computer has qubits. That is to say: BQPSpace = PSPace.

(I think the trick is to represent the quantum computation as a chain of matrix multiplications. Instead of computing the intermediate matrices or states, which would take too much space, you slowly but surely iterate over all the ways each path through the matrices can contribute to the probability of a final state and return the state with that probability.)

Informally speaking, the reason quantum computers might take so much more space (we haven't actually proven this) is that their state is a weighting of each possible classical state. With $n$ bits you have $2^n$ classical states, so you need $2^n$ weighting factors to represent $n$ qubits (unless you're somehow clever about it).

This question is a bit more complicated than you might expect, because the number of bits you need depends on whether or not you care about how long the computation takes.

If you're willing to wait an amount of time that's exponentially longer than the quantum computer would take, then you can simulate a quantum computer with a classical computer without using exponentially more space. Sacrificing time makes the space overhead polynomial; BQPSpace is equal to PSPace.

(I think the trick is to represent the quantum computation as a chain of matrix multiplications. Instead of computing the intermediate matrices or states, which would take too much space, you slowly but surely iterate over all the ways each path through the matrices can contribute to the probability of a final state and return the state with that probability.)

Intuitively speaking, the reason you'd expect quantum computers to take so much space classically is that a quantum state is a weighting of each possible classical state. With $n$ bits you have $2^n$ classical states, so you need $2^n$ weighting factors to represent the state of $n$ qubits... unless you find a way to be clever about it.