Comparing complexity of digital and analog quantum computation

Question

The complexity of an algorithm run on a digital quantum computer is quantified, roughly, by the number of elementary gates in the corresponding circuit. Can one similarly quantify the complexity of an analog algorithm?

Take for example adiabatic computation. There, the driving to the target Hamiltonian must be sufficiently slow so that the adiabaticity criterion is satisfied. This bounds the minimal time for successful completion of the algorithm. However, on the surface, the two notions of complexity or time, required for computation, seem very different.

Is there a way to compare the digital and the analog computation complexities? Do we believe that asymptotically they must have the same complexities, or perhaps analog computations can sometimes be faster?

Answer 1

You could compare this with how -- on a regular, classical computer -- there are two different notions of time: clock cycles and wall time. The programmer who works with C code or assembly sees discrete operations that happen on a schedule. The electrical engineer planning signal delays in the CPU knows that current is flowing everywhere and evolving continuously with time.

To convert between the two, we have a speed (the clock speed of the CPU).

If you had an analog circuit to compute something you wanted, you would measure it in terms of the time needed to compute your solution, and then compare that with the wall-clock time of your digital computer.

In the end, "digital" quantum computers -- although I would avoid that term, and perhaps saying "gate-based quantum computers" -- are still really analog devices. Google's Sycamore processor, for instance, uses crafted continuous pulse shapes that span a few microseconds and excite the system in a particular way. While the pulse is occurring, the system undergoes continuous time evolution. In the end, there's some time per gate, and that gives you a wall-clock time.

Similarly, adiabatic computing ends up taking some amount of time. That's how you compare them: with the actual amount of time.

When complexity theorists compare algorithms on gate-based and adiabatic quantum computers, everything is $O(something)$ anyway, and the exact constant (the clock speed) doesn't matter. An adiabatic algorithm could be considered efficient if its time scales linearly with the amount of gates.

There is one subtlety, and that is the question of simultaneous gates. In the gate model, if you have $n$ qubits, you might apply $n$ gates simultaneously; you can choose to count this as $n$ gates, or as 1 gate. A particular analog quantum computer may only be able to carry out the gates one at time, in which case counting them as $n$ separate gates might make more sense in the comparison. In terms of the impact of real-world time, it comes down to a matter of hardware, if the hardware permits simultaneous gates or not.