> If your vector space is too big to even represent in classical memory, you might still be able to work with it on a quantum computer.
Quantum computers don't have any space advantage, I thought?
Quantum computers don't have any space advantage, I thought?
You can represent any unit vector in a vector space with 2^n basis elements using only n qubits.
Constructing an arbitrary vector might not be more efficient than doing it on a classical computer, but constructing certain vectors that would probably be very large and/or unwieldy on a classical computer is possible. For example, it’s easy to represent any single standard basis vector in a vector space with size 2^64 on a classical computer; just use a list of (64-bit word to describe which basis vector you’re talking about and a weight). Now go ahead and try to use that same representation for a Fourier transform, and you’re out of luck. But this is no problem on a quantum computer. You just end up with a 64-qubit system that has a non-zero value for all of those 2^64 basis states (using only 64 qubits). You can also construct the circuit required to do the Fourier transform with ~64log(64) gates.
So for this problem, there’s definitely a space advantage. The trouble is that most of these advantages don’t generalize in any obvious way. Maybe there’s even a representation on classical computers that’s equally efficient and we just haven’t found it yet.
And as you mention below, this isn’t useful for arbitrary linear operations (many of them seem to be just as expensive on a quantum computer as on a classical computer) but there are certain known-to-be-useful linear operations that are extremely cheap to represent compared to what we know how to do on a classical computer.
A quantum computer, with a qubit register 0101, can be put into a superposition state between all 4 qubits, where the state of the qubit register is ALL 2^4 different configurations simultaneously....now scale that up to 50-100-1000 qubits and you get the idea. The quantum computer has a ridiculous advantage in terms of holding state spaces.
The point of the space argument I was making was that, if you need N bits of space to represent the input/output in classical computers, you should still need (I'm not sure if it's the case, but I don't see why it's not) Ω(N) qubits to do the same representation in a quantum computer.
The quantum bullshit fallacy is that, since an entangled N-qubit is represented as a 2^N-dimension vector with complex arguments, it's really a computation on 2^N elements in O(1) time. The first sign that this is fallacious is that the basis here isn't of size 2^N but of size 2^N - 1. We're still only capable of reading N bits of information out of an N-qubit register; the fact that classical simulation requires a much larger state space to compute the probability doesn't mean that there's an inherent ability to freely vary through all of those states to represent the entire state space.
So one very simplified model to think of what quantum computation is that you can do parallel operations to a distribution over your 2^N vector of classical bits, but you don't get to specify an arbitrary starting distribution, you can only start with relatively 'simple' distributions.
This restriction is what makes the claim 'you can compute over 2^N values simultaneously' at best very incomplete — yes, you can do that, as long as you're fine not being able to start from arbitrary starting values. But this is a big restriction!
A superposition is (a bit of an oversimplification since there are also complex numbers involved and a linear constraint) is in some sense a probabilistic distribution over the possible (classical) values that you get when you measure those N qubits.
E.g. if you measured this N-qubit state many times, which of the 2^(N-1) possible superposition values would you get? Would it be the uniform distribution? Biased towards particular classical bit patterns?
Note that there are 2^(N-1) possible classical bit patterns, so an arbitrary collection of these patterns would take O(2^N) operations to define.
> I'm definitely not saying you get the answer to every problem in a single evaluation step
Yes, but my point is that if your input is an arbitrary collection of classical N-bits, then in general you will require an exponential number of quantum operations to set stuff it into an N-qubit initial state, which means you get zero speedup.
Quantum computers only see speedup on inputs that require a relatively small number of quantum operations to set up. 'Small' could mean polynomial. But it's true that the space of 'easy to set up' initial N-qubit states is much smaller than the space of all possible N-qubit states, which is why a quantum computer cannot simply considered 'a magical computer that computes on 2^N bits at once' without considering how you get those bits in or out of the damn thing.
Can you provide a reference for this? My understanding is that you can efficiently setup qubits using a hadamard transform
The span of qubit states reachable in a polynomial number of Hadamard transform operations from the starting state is much less than all possible qubit states.
This follows immediately from information-theoretic principles. There are 2^(2^N-1) possible 'collections' of 'classical bits' representable by N qubits. Therefore it takes 2^N-1 bits of information to represent, but since the Hadamard transform is basically linear, we can see (in a very handwavy way) that only a polynomial number of possible states is reachable from a polynomial number of quantum gate operations.
we can create an n-qubit superposition containing 2n component eigenstates. These eigenstates represent all the possible bit strings one can write using n bits. The importance of this capability is often overlooked. But, in reality, it is one of the most important tricks of quantum computing as it gives is the ability to load exponentially many indices into a quantum computer using only polynomially many operations. Had Nature been unkind, and had we had to enter the different bit-strings individually, as we do in classical computing, then quantum computing would have had far less potential for breakthroughs in computational complexity."
I'm just talking about loading a quantum register, there are other issues with gate times and decoherence.