4
$\begingroup$

I am currently reading various survey papers in Quantum Machine Learning, such as "Quantum Machine Learning" by Biamonte, Wittek, Pancotti, Rebentrost, Wiebe, and Lloyd. To me, it is not clear when they are talking about Adiabatic Quantum Computing or the Logic Gate approach.

Example: "The quantum basic linear algebra subroutines (BLAS)—Fourier transforms, finding eigenvectors and eigenvalues, solving linear equations—exhibit exponential quantum speedups over their best known classical counterparts [8, 9, 10]."

Question: Are these people always talking about one of the two technologies (if so, which?), or are they discussing them interchangeably?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

In this particular one (by quickly overlooking), they refer mostly to the logic gate approach. But nothing prevent them from talking about both. It depends on the algorithm and on which original model it was thought/designed on. Generally, if it is linear algebra based, it will be the logic gate approach. If they refer to optimization of a QUBO, they will talk about a D-Wave quantum annealer (should be mentionned in an introduction part), a specific case of quantum annealing.

If you want to be sure which one for each algorithm, the best way when it is not clear is looking at the references. That helped me a lot figure out details like that.

Improve this answer
$\endgroup$
1
  • $\begingroup$ FYI: Selected this as the answer, as it provides a strategy to distinguish the technologies. Please do look at @DaftWullie his answer for interesting insights on the Big O implications when comparing these. $\endgroup$
    – Thomas Hubregtsen
    Feb 6, 2019 at 6:45
6
$\begingroup$

I've not looked at those papers specifically, but there are several different models for quantum computation (see here), including the gate model and the adiabatic model, which are polynomial time equivalent. That means if one has an exponential speedup, so does the other. The discussion should be interchangeable.

The title, if not the question body, also asks about quantum annealing. So, to summarise the comments:

  • Adiabatic QC is a special case of quantum annealing. So, in that sense, since adiabatic is one of those interchangeable ones, so is quantum annealing.
  • However, when people talk about quantum annealing, they are often thinking beyond the adiabatic case, with non-adiabatic trajectories, finite temperature etc. Here, the answer is simply we don't know if it is polynomial time equivalent with the other models. Many people believe that it has equivalent computational power, but it has not been proven.
Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks. Does this answer hold for both Quantum Annealing and Adiabatic computing with regards to Quantum Annealing? $\endgroup$
    – Thomas Hubregtsen
    Feb 1, 2019 at 14:10
  • $\begingroup$ I am not aware of it applying to quantum annealing, because I am not aware of any proofs, just hopes. As stated in one of the answers, quantumcomputing.stackexchange.com/a/4228/1837, "There are no formal results about how quickly you can change your Hamiltonian to achieve this: the subject appears mostly to consist of experimenting with a heuristic to see what works in practise." $\endgroup$
    – DaftWullie
    Feb 1, 2019 at 16:01
  • $\begingroup$ As stated in that answer, QA is a generalization of AQC; more specifically AQC is the closed-system limit of QA (no temperature, no noise). So yes, in principle the models are interchangeable. But in practice one cannot assume that a QA processor effectively implements AQC. $\endgroup$
    – Andrew D. King
    Feb 1, 2019 at 16:12

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.

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