7
$\begingroup$

This question is a follow-up on this one, with the hope of getting more specific clues, and was motivated by this answer by user Rob.

Also please note this posts that handle the topic of QA in much more detail:

https://quantumcomputing.stackexchange.com/a/1596
https://quantumcomputing.stackexchange.com/a/4228

In D-Wave Systems' webpage, we can read a description of how an annealing QPU like their 2000Q flagship is able perform optimization on a given distribution by regarding many paths simultaneously, which makes the optimization process more robust against local minima and such.

After that, they claim that "it is best suited to tackling complex optimization problems that exist across many domains", and they cite (among others), optimization, machine learning and sampling / Monte Carlo

Furthermore, in Wikipedia, we see that

Quantum annealing (QA) is a metaheuristic for finding the global minimum of a given objective function over a given set of candidate solutions [...]. Quantum annealing starts from a quantum-mechanical superposition of all possible states (candidate states) with equal weights. Then the system evolves [...] The transverse field is finally switched off, and the system is expected to have reached the ground state.


At this point, we see that both explanations (with different detail levels) address the question of how annealing can help non-convex optimization (among other things). And that isn't even specifically related to quantum computing since simulated annealing stands on its own. But it is D-Wave claiming their hardware can help to perform sampling.

Maybe the connection is obvious and I'm missing it, but I think sampling is a distinct enough task from optimization to require its own explanation. The specific questions that I have are:

  • Given some data following a possibly unknown distribution, how can the D-Wave be used to perform sampling on it? What are the constraints?
  • To what extent is it advantageous against other SoTA classical sampling algorithms like, say, Gibbs?
  • Are the possible advantages specific to annealing QPUs, to any QPUs or a general property of simulated annealing?
$\endgroup$
  • $\begingroup$ Chancellor proposes how to do sampling around specific states with quantum annealing. arxiv.org/abs/1606.06800 $\endgroup$ – Andrew O Apr 8 '18 at 22:03
1
$\begingroup$

This answer reflects my understanding of what D-wave have to say about this, in the 2013 whitepaper they link to: Programming With D-Wave: Map Coloring Problem


To back up the question, we find once again the claim:

"superposition" states [...] give a quantum computer the ability to quickly solve certain classes of complex problems such as optimization, machine learning and sampling problems.

And the explanation for the optimization problem:

The processor considers all the possibilities simultaneously to determine the lowest energy required to form those relationships. Because a quantum computer is probabilistic rather than deterministic, the computer returns many very good answers in a short amount of time - 10,000 answers in one second. This gives the user not only the optimal solution or a single answer,
but also other alternatives to choose from.

Then, the statement that the QPU naturally returns samples:

If the D-Wave quantum computer has no registers or memory locations, a natural question arises: how do we learn anything from having executed a quantum machine instruction? The answer is that we are given samples from a distribution, as a side effect of executing the QMI (quantum machine instruction).


But how? First, they explain what is the interface for such QMIs:

  1. "The D-Wave system has many qubits [...]. The programming model does not allow the programmer to directly set the value of these qubits"

  2. Instead, the state of the $q_i$ qbits can be influenced by setting a weight $a$ for each qbit, and a weight $b_{ij}$ (called coupler) for each connection between any 2 qbits. The qbits are linearly combined into an "objective function that will define the distribution from which our samples will be selected": $O(a,b;q) = \sum_{i=1}^N{a_i q_i} + \sum_{<i,j>}b_{ij} q_i q_j$.

  3. "Each QMI consists of exactly the $a$ and $b_{ij}$ values that appear in the [...] objective function"


And then they describe the protocol for such QMIs:

As a programmer, it is our job is to encode the various possible solutions to an optimization problem in the qubit variables $q_i$. Then we translate the constraints in our optimization problem into values of the weights $a_i$ and strengths $b_{ij}$ such that when the objective is minimized the qubits will satisfy the constraints.

In this context,

  • "Each sample is simply the collection of $q_i$ values for the entire set of qubits which enter into our problem".

  • "The distribution is an equal weighting across all the samples that give the minimum (or slightly above in practice) value of our objective function".


So as far as I understood, three things are known to the programmer in beforehand:

  1. The set of constraints (weights and couplers)
  2. The distribution's domain (encoding of the qbits)
  3. The fact that the distribution is a linear mixture model

Then, running the program once will return a distribution which is by itself an average of all the possible optimal samples in the domain that satisfy the constraints.

And now I will try to answer my questions:

  • Given some data following a possibly unknown distribution, how can the D-Wave be used to perform sampling on it? What are the constraints?

I will start with the constraints:

  1. The distribution has to be representable as a linear mixture model of qbit distributions.
  2. The hardware has to be capable of encoding the whole domain of the distribution
  3. The programmer has to be able to express the desired distribution as a combination of sets of constraints within the mixture model. Therefore the distribution has to be implicitly known, but not explicitly: this suits in fact very well machine learning and data-driven workflows.

Given this assumptions, it should be possible to extract the probability density function by running the program once per constraint set, and performing the pertinent combination. Note that the linearity of the mixture model is somehow a limitation, but also has its advantages regarding such combinations.

  • To what extent is it advantageous against other SoTA classical sampling algorithms like, say, Gibbs?

The advantage comes from the speedup that "superimposed" states give by enabling a single program's output to collapse multiple samples. But there is one big caveat: the output returns all the minimum states for the given constraint. This means that the speedup depends on the programmer's ability of encoding the constraints in a way that collapse as many outputs as possible. Without getting into big-O, this doesn't seem trivial at all to me.

  • Are the possible advantages specific to annealing QPUs, to any QPUs or a general property of simulated annealing?

I don't know about other QPUs (help very welcome), but regarding Wikipedia's pseudocode for simulated annealing we see that the output is a single sample. So, given the big caveat discussed before, this is already the worst-case scenario for a D-Wave sampler.


POSSIBLE APPLICATION EXAMPLES:

  • This related paper (linked by user hopefully coherent) presents an algorithm that could be a candidate for this case: At the end of page 2,

    "We address the first term in (1) by describing a quantum procedure to efficiently sample the eigenvalues of an $n\times n$ Hermitian matrix $A$ uniformly at random"

It would be very interesting to see if/how the constraints for eigenvalues can be encoded as the above discussed QMIs.

  • Insert here some example for the encoding of some data-driven setup like "given this $N$-dimensional dataset, find the projection or embedding that minimizes some non-convex objective" into such QMIs.
$\endgroup$
  • $\begingroup$ Please let me know if I didn't get it properly! Or if I got it right, any reference to research concerning how to represent distributions as sets of constraints would be very welcome $\endgroup$ – fr_andres SupportsMonicaCellio Apr 8 '18 at 0:41
  • 1
    $\begingroup$ The "more comprehensive explanation" is doing you a disservice, I'm afraid --- it really isn't explaining anything very well. They're completely omitting anything about what makes superpositions different from probability distributions, implying somehow that it is the mere fact that things are being done in superposition that gives an advantage, which is untrue. Your summary reflects this lack of explanation on their part, and describes things which would be equally true of a randomised algorithm. $\endgroup$ – Niel de Beaudrap Apr 8 '18 at 9:19
  • $\begingroup$ A rule of thumb: if someone offers you an explanation of quantum computation, but doesn't show you any math behind what it is actually doing, they aren't trying to teach you something: they are trying to sell you something. $\endgroup$ – Niel de Beaudrap Apr 8 '18 at 9:21
  • 1
    $\begingroup$ Because the idea that I got from this is that the advantage is in becoming a superposition of answers that satisfies the constraints. If true, I could totally see an advantage in that! Also true is, that the prior qbit distributions aren't described anywhere, but I thought this would be either irrelevant or evident or off-topic. $\endgroup$ – fr_andres SupportsMonicaCellio Apr 8 '18 at 13:29
  • 1
    $\begingroup$ In any case I don' intend to accept my answer since I agree that it is not "comprehensive" (I will edit that bit). I am interested in how QPUs could help sampling in the context of bayesian learning, and this is all I managed to grasp yesterday evening, but I will keep looking, would be very happy to see a more technical explanation :) $\endgroup$ – fr_andres SupportsMonicaCellio Apr 8 '18 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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