# Quantum fourier transform with classical vibrations

Is there any difference in effect between a quantum circuit and a carefully constructed analogue one relying on interference? For example, why couldn't I take a series of $$N$$ carefully shaped pipes, split a sound source between them, and build, say, a quantum Fourier transform circuit with classical versions of Hadamard and phase shift gates? For example, it would be easy to shift phase by extending the length of a pipe with a sufficiently smooth spiral. I recall that you can invert the phase with a reflection or a phase shift set to 1/2 the wavelength of the sound in the pipe. You could split and combine outputs by splitting and combining pipes. Then, instead of tallying up clicks on different channels (as in a quantum computer), you could just measure the power coming through each of the output channels.

I'm not saying this is necessarily practical--if nothing else you'd obviously have better bandwidth at higher frequencies than sound could propagate through most media. I got the sense there had to be some difference in effect between this hypothetical scenario and a real quantum computer. Could anyone help identify it or else confirm the effect is, in fact, the same?

The problem is that the classical analogue has to have physical elements and operations for each amplitude, instead of for each qubit.

Here is a quantum circuit for the 16-amplitude Fourier transform:

Here is a butterfly diagram for the 16-state Fourier transform (from here):

Each hadamard operation in the quantum circuit is an entire butterfly layer in the classical diagram.

A classical system has to have storage and/or operations for each line in the butterfly diagram. Whereas a quantum computer only needs the storage and operations from the smaller quantum circuit. This disparity gets exponentially worse as the number of qubits goes up.

(The downside is that the quantum system can only sample from the output distribution. The classical system has full access to the output distribution because it has the whole thing stored in memory.)

• Thank you for the great explanation, but raises one new question for me at least: could the reduction in channels be attributed to the number of internal degrees of freedom of the field propagating the signal? For example, if I replaced my sound analogy with laser light (or perhaps even microwave radiation), I could get an extra bit per line by playing with polarization. This seems quite similar to what you would be doing with the quantum circuit. Jul 7 at 13:14
• @AlexEftimiades it's really not similar at all. Adding one qubit doubles the number of amplitudes. Using polarization as a bit will double the number of bits... once. But then you have to find two more bits in your photon to keep up with the next qubit. Then four more. Then eight more. Jul 7 at 15:32
• I think I see. The question becomes why this laser setup breaks down for continuous feeds. If I take the quantum setup, stream input through it, and record a time average, I'll end up recording a product of marginal distributions on the output bits. The quantum Fourier transform however seems designed to produce coefficients associated with joint distribution of output bits. This requires separating the inputs into pulses and recording each output state as a whole. The input however just starts as a superposition of phases indexed in binary by state. This seem right? Jul 7 at 19:46
• @AlexEftimiades Yes, the correlations between the outputs is important. For example, in Shor's algorithm, the output bits encode integers near a multiple of N/2^q where N is the number to factor and q is the number of qubits the QFT is applied to. If the output bits were uncorrelated, the output couldn't be guaranteed to be near multiples of N/2^q. Jul 7 at 22:32