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:
"The D-Wave system has many qubits [...]. The programming model does not allow the programmer to directly set the value of these qubits"
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$.
"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:
- The set of constraints (weights and couplers)
- The distribution's domain (encoding of the qbits)
- 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:
- The distribution has to be representable as a linear mixture model of qbit distributions.
- The hardware has to be capable of encoding the whole domain of the distribution
- 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.
