2
$\begingroup$

I've read up on quantum annealing, and particularly on the way it is done by companies like D-wave. I think I understand how it works and how it harnesses tunneling to find global optimal in a given energy potential.

But the elephant in the room is: How can it be of any use? What is the point of looking for an optimum in a potential which you yourself have created? If the potential were a black box, then I could see some use. But clearly the potential is prepared in a controllable fashion, so that seems to defeat the purpose.

Please clear up my confusion.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Are you asking why it's useful to find the minimum of a function you created yourself? Suppose you're trying to figure out how to build a house with the minimum amount of money. You can write a function for the amount of money needed where the building materials are the inputs. That's a function you created, but you obviously would like to minimize it. $\endgroup$
    – DanielSank
    Commented Jul 3, 2017 at 1:55

2 Answers 2

Reset to default
1
$\begingroup$

You are thinking that the "potential" takes the form of a completely arbitrary, unstructured function of the entire field configuration. Finding the minimum of this kind of function is an example of what in theoretical computer science is called "unstructured search." Indeed, quantum annealing doesn't give much of a speedup for unstructured search; it has been proven that Grover's algorithm gives the best possible quantum speedup for unstructured search, which is "only" a square-root rather than an exponential speedup.

(Actually, this isn't really correct. Finding the minimum of a completely arbitrary unstructured function is even harder than the usual decision-problem formulation of unstructured search, because it lies even outside of the search equivalent of the complexity class NP. That's because even if a quantum computer were to give you an answer, the only possible way to check it would be to effectively repeat the entire search again. So in the real world, such a quantum computer might not be very useful, because there would be no practical way to check whether its answer was correct or the computer had a bug. Also, if the search space were exponentially large, then even loading the problem statement into the computer could take longer than the age of the universe - let alone actually having the computer solve it.)

But this isn't the kind of potential that's constructed in quantum annealing. The potential isn't arbitrary but is highly structured. The prototypical problem that's attacked by QA is the Ising spin-glass problem. The details aren't important, but the point is that only a exponentially tiny fraction of all possible potentials can be formulated as an Ising spin glass. (Concretely, specifying an Ising spin glass Hamiltonian on a system of $N$ spins only requires specifying $(N \text{ choose } 2) = (1/2) N (N-1) \sim N^2$ different parameters, while a completely arbitrarily Hamiltonian requires $2^N$ parameters to specify.) Since you've specified the $\sim N^2$ different couplings but not the explicit $\sim 2^N$ different possible energies, you don't really "have an exact handle on" the potential, even though you formally know it exactly.

As an analogy, consider the Traveling Salesman problem: if I were to just list a bunch of completely trips and their lengths, and asked you to find the shortest, then this (unstructured search) isn't a very interesting problem mathematically. Clearly the only possible solution is to go through every trip one by one and keep the shortest one you've found so far. Unsurprisingly, quantum computers (of any type, not just annealers) can't give you much of a speedup on such a structureless problem. But if I instead gave you a list of distances between cities and asked you to find the shortest route that connects them all (the usual formulation of the problem), then (a) the information need just to state the (structured search) problem can be exponentially compressed, (b) there are many more math tools we can use to attack it, and (c) quantum computers might be vastly more efficient than classical computers at finding the shortest path. (I say "might" because, unlike the Ising spin glass problem, virtually no one in the theoretical CS community thinks that quantum computers will be able to efficiently solve the Travelling Salesman problem.)

Improve this answer
$\endgroup$
12
  • $\begingroup$ Thanks for the detailed answer, but I'm afraid it still does not address my question. I am not making any assumptions as to whether the potential function is arbitrary or structured. Besides, what do we even mean by "structured"? What metric are we talking about? Entropy? Quantum purity? I still don't see how any of that matters. The D-wave "computer" prepares a potential (structured or not) in a controllable manner. It "knows" exactly how to distribute the intensities and thereby the location of all the optima. Do you see what I mean? $\endgroup$
    – Tfovid
    Commented Jul 4, 2017 at 1:16
  • $\begingroup$ @Tfovid They don't prepare the potential directly. They directly prepare the couplings in the Hamiltonian. This uniquely determines the potential, but only through an incredibly difficult computation that cannot be done in practice. So they don't know the locations of the optima at all times. $\endgroup$
    – tparker
    Commented Jul 4, 2017 at 1:35
  • $\begingroup$ @Tfovid You need to conceptually distinguish between the length-$N^2$ list of Hamiltonian couplings, which gives you the formula for calculating the potential, and the potential itself, thought of as a list of $2^N$ diferent energies. They are mathematically isomorphic, because given one you can in principle find the other with enough computing time. But in practice they're completely diferent, because the time to do the conversion is impractically long. The D-Wave programers only know the former. Having the list of couplings does not allow you to know the values of its minima in practice. $\endgroup$
    – tparker
    Commented Jul 4, 2017 at 1:38
  • $\begingroup$ @Tfovid Perhaps we should back up and clear up a more basic question. Do you understand the general concept that it can be difficult to find the minimum of a known function? (I'm not trying to be snarky, that's an honest question.) If you do, then the answer to your question seems clear. $\endgroup$
    – tparker
    Commented Jul 4, 2017 at 1:45
  • $\begingroup$ I understand the difficulty of finding the minimum of a known function. Just because I have a well-defined, closed-form expression of some function, does not mean I can easily read out its global minimum. That said, if I encode that function in a physical system, then I know its value at every point. E.g., I know the potential of every atom in my lattice since I have prepared them myself. The key point that I'm trying to get across is that I have full control over every atom in my system. I have prepared it. I know where all the optima are to begin with. $\endgroup$
    – Tfovid
    Commented Jul 4, 2017 at 13:49
0
$\begingroup$

The problem of finding the ground state of an Ising spin glass (the problem that D-Wave allegedly solves) is NP-complete, so if we can solve that, then we can efficiently adapt our solution to solve any problem in the complexity class NP - which constitutes an enormous array of useful problems. See here for concrete algorithms for translating a solution to the Ising spin glass into solutions to more useful problems.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I understand that, but it still doesn't explain why we would need to optimize a function (i.e., potential) which we ourselves have prepared in a controllable fashion. If I am going to draw the x^2 as my potential, then presumably, I already know that it will be smallest at x = 0 and that defeats the purpose of minimizing it. $\endgroup$
    – Tfovid
    Commented Jul 3, 2017 at 14:20
  • $\begingroup$ @Tfovid If the function is a simple as $x^2$, then sure. But as DanielSank said, for more complicated functions the minimum can be far from obvious, even if we know the function exactly. Optimization problems can be extremely challenging. Consider that in the Traveling Salesman problem, a canonical example of a "hard" computational problem, the cost function is known exactly. $\endgroup$
    – tparker
    Commented Jul 3, 2017 at 18:11
  • $\begingroup$ I don't see how the complexity of the function has anything to do with it. If you're going to controllably create a potential function (via spins systems or what not), then clearly you should know where every potential should lie, including the lowest/highest one. If you don't, then you're not the master of your own potential function and then we're talking about something else. $\endgroup$
    – Tfovid
    Commented Jul 3, 2017 at 22:20
  • $\begingroup$ @Tfovid Yes, you do indeed "know exactly where every potential [lies], including the lowest/highest one." But you don't know which one is the lowest/highest one. The domain of the potential function is so enormously large that simply check each value one by one could take longer than the age of the universe. The difficultly of finding the minimum value of a known function has nothing to with how "controllably" that function was experimentally realized. $\endgroup$
    – tparker
    Commented Jul 3, 2017 at 22:24
  • $\begingroup$ I'm afraid we're "talking past each other" here. The "enormity" or complexity of the potential function is irrelevant to the problem. You've created the potential function yourself; you've tweaked every spin/atom/whatever yourself to create it and you therefore know it's value at every point in the first place. What is then the point of looking for it a posteriori using tunneling or whatever other method. As I mentioned in my original post, if the potential were a black box, then annealing for optimization would make sense. But that's not what I gather from what D-wave does. $\endgroup$
    – Tfovid
    Commented Jul 3, 2017 at 22:31

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.