[codekilla]

> 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

Can you provide a reference for this? My understanding is that you can efficiently setup qubits using a hadamard transform

[smallnamespace]

Yes, but the Hadamard transform is essentially a linear operation.

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.

[codekilla]

This is verbatim from 'Explorations in Quantum Computing' by Colin P. Williams: "The utility of the Hadamard gate derives from that fact that by applying, in parallel, a separate Hadamard gate to each of n qubits, each initially in the state |0⟩, 1 H|0⟩⊗H|0⟩⊗···⊗H|0⟩= √ |j⟩ (2.20)

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.