3
$\begingroup$

I'm trying to understand how computational complexity is quantified in adiabatic quantum computing.

With the circuit model, computational complexity is simple: count the number of times you queried your blackbox. This can be easily related to classical complexity theory and compared to classical algorithms (i.e $O(N)$ for classical unstructured search and $O(\sqrt{N})$ with Grover's).

But in the adiabatic model, Wikipedia claims that the runtime is the amount of time it takes to complete the evolution of the Hamiltonian given as $T=O(1/g^2_{min})$ where $g_{min}$ is the minimum spectral gap of the time varying Hamiltonian. I don't see an obvious way of comparing the computational complexity of the adiabatic model with the circuit model.

How can we compare the computational complexity of the adiabatic model to the circuit model in an "apples to apples" way? It seems like the number of seconds something takes is a bad measure of how well it performs generally. It's like saying you ran a very complex algorithm (with $N=2^n$ inputs) on a supercomputer in 1ns, so it's computational complexity is $O(1)$.

Thanks for the guidance.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Initially, this is a minor point but what you refer to as the "circuit model" I would call the "query model". For example we don't need to instantiate Grover's algorithm with a particular circuit for the oracle; Grover's theorem is simply that the number of queries to the oracle (however it's instantiated) is $O(\sqrt N)$. In contrast, however, it's reasonable to refer to the circuit complexity of Shor's algorithm (as we in particular instantiate his algorithm with, for example, the circuits for modular exponentiation). Discussions about this distinction can lead to some bruhaha.

Secondly regarding the adiabatic model in particular, there is a polynomial equivalence between the adiabatic model and the standard (gate or circuit) model of computation. Going one way, this means that we can take an adiabatic algorithm that runs in time $O(\mathrm{poly}\ n)$, and actively construct a circuit of length $O(\mathrm{poly}\ n)$.

Lastly when comparing different models we refer to the asymptotics of the resources and how these scale with the input size $n$. For example, in Shor's algorithm we can discuss how the number of gates grows with the number of digits; in Grover's algorithm we can discuss how the number of queries grows with the size of the database; and in the adiabatic algorithm we can discuss how the time-length of the evolution grows with the number of qubits. It is reasonable to state that, asymptotically, each of these may grow exponentially, or polynomially, or logarithmically, etc.

For the particular example of "the number of seconds", you don't make any reference to the input size $n$. Thus, it's not justified to say that:

It's like saying you ran a very complex algorithm on a supercomputer in 1ns, so it's computational complexity is $O(1)$,

because you haven't indicated what is the size of the input to the complex algorithm, and how this complex algorithm varies with $n$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Hi Mark, thanks for the response. You say that "you haven't indicated what is the size of the input to the complex algorithm". I thought it was assumed that generally the input size to an algorithm is $N=2^n$, but for clarity I will edit my post. When you say "circuit of length", what does that mean? That does not seem equivalent to the number of queries nor the amount of time an algorithm takes to run. I don't intuitively see how you can claim a polynomial equivalence when you are comparing time to length... like apples and oranges. $\endgroup$
    – anon
    Apr 25 at 14:10
  • $\begingroup$ "in Grover's algorithm we can discuss how the number of queries grows with the size of the database". There is an adiabatic Grover's algorithm. Can you explain, in that particular example, how the size of the database can be related to the time it takes to evolve a Hamiltonian? $\endgroup$
    – anon
    Apr 25 at 14:14
  • $\begingroup$ @Rydberg thanks for your revision - that helps to even emphasize the point. (Usually the input is $n$, not $N=2^n$). How would your complex algorithm behave for a larger database? If it always and only takes 1 ns, regardless of the size of the database, then it's justified in saying that it's $O(1)$. But, if it takes a longer time for a larger database, then it is not justified to say that it's $O(1)$. And, regarding an adiabatic version of Grover's algorithm, as the size of the database grows, the length of time for the evolution grows as the square root of this length... $\endgroup$
    – Mark Spinelli
    Apr 25 at 14:44
  • $\begingroup$ Thanks Mark for the follow-up. I still don't understand the polynomial equivalence between the adiabatic and standard gate model. Can you explain how we are relating circuit length/queries to a unit of time in an equivalent manner? $\endgroup$
    – anon
    Apr 25 at 17:33
  • $\begingroup$ Well, the longer or deeper the circuit, certainly the longer it would take to execute. If it takes 5ns to execute a series of microwave pulses or laser pulses or what-have-you to perform a single query in Grover's algorithm, then it would take 5ns * N to execute N such queries. Remember in a circuit diagram time (actual clock time, e.g. in ns) goes from the left to the right - a wider circuit will take a longer time. $\endgroup$
    – Mark Spinelli
    Apr 25 at 18:07

Your Answer

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