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?


1 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.

  • $\begingroup$ Thanks for an elaborate answer! I agree that what matters in the end is wall time. I think there is one piece missing to complete my understanding. Is it true that it is always possible to simulate an evolution of a quantum system for time $T$ by a circuit with $O(T)$ gates in it? $\endgroup$ Jul 29, 2021 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.