Generative quantum advantage for classical and quantum problems

Recipe for sampling from an IDQNN

1. Prepare each qubit on the lattice in the \(\ket{+}\) state.

2. Entangle the qubits by performing controlled-Z gates between some pairs of nearest-neighbour qubits on the lattice. If the qubits are horizontal neighbours on the lattice, a CZ is always applied.

3. Perform a single-qubit Z rotation \(U_{z}(\theta_{ij})=\exp(-\frac{i}{2}\theta_{ij}Z)\) with parameter \(\theta_{ij}\) on each of the qubits

4. Measure all qubits in the X basis to produce outcomes \(y_{ij}\)

We can depict this graphically as follows.

Note that this is not a circuit diagram, but a graphical representation of the circuit description above: qubits are denoted by black dots, CZ gates are lines between dots, the angles specify the single-qubit rotations, and the blue \(y_{ij}\) are the X-measurement outcomes. We’ll also use the vector \(\boldsymbol{y}\) from now on to denote all the \(y_{ij}\).

The above corresponds to a circuit acting on a 2D lattice of 12 qubits, and this structure corresponds to a shallow circuit since the circuit depth does not depend on the size of the lattice. However, we can map this onto an equivalent deep 1D circuit with only 3 qubits by viewing the circuit as a measurement based quantum computation (MBQC) recipe. When viewed from this perspective, the horizontal dimension of the lattice becomes a time axis, so that at time 0, the system consists of just three qubits (the first vertical axis) prepared in the \(\ket{+}\) state. After applying all CZ and rotation gates that involve these qubits and measuring them in the X basis, the state is teleported to the next line of three qubits (the precise state will depend on the measurement outcomes \(y_{11}\), \(y_{12}\), \(y_{13}\)). Repeating this process until we arrive at the end of the lattice therefore defines a type of stochastic quantum circuit acting on three qubits. The precise way to make this mapping is well known from MBQC theory, and is a bit tricky (see Appendix H2 of their paper [1]), so we won’t bore you with the details here.

If you apply the mapping to our example IDQNN, you find the following circuit:

The circuit structure for layers 2 and 3 is the same as for layer 1, where the CZ structure is determined by the vertically acting CZ gates that appear in the second and third vertical axis of the lattice. The inputs to the Z gates are classical controls, i.e. the gate is applied only if \(y_{ij}=1\).

To generate samples from this deep circuit we do the following:

Recipe for sampling from the deep circuit

1. Generate all bits \(y_{ij}\) for \(i<4\) uniformly at random using a classical random number generator.

2. Run the above circuit, controlling the Z gates on these bits.

3. Measure the output of the circuit to obtain the final three bits \(y_{41}\), \(y_{42}\), \(y_{43}\).

One can show that the distribution \(p(\boldsymbol{y})\) obtained with the above recipe is identical to the one we described for the IDQNN, and so the two methods are indistinguishable if just given samples \(\boldsymbol{y}\).

If these two circuits lead to the same distribution then why did we do this? The reason is that qubit counts on quantum hardware are still limited. By implementing the deep 1D circuit on a few qubits however, you can simulate the distribution of a 2D shallow circuit on many more qubits (the authors call this circuit ‘compression’). This trick is used to simulate a shallow IDQNN circuit on 816 qubits using a deep circuit with just 68 qubits. To do this, they actually work with a deep circuit on a 2D lattice, and map it to a shallow circuit on a 3D lattice. This obviously complicates things a bit (and makes drawing pictures a lot harder!) so we will stick to the 2D vs 1D example above; in the end, it will contain everything we need to understand the result for higher dimensional lattices.

Recipe for sampling from an IDQNN with inputs

1. Prepare each qubit in either the \(\vert + \rangle\) or \(\vert 0 \rangle\) state, depending on \(x\).

2. Perform steps 2-4 as before.

In order to be able to prove the result, the choice and distribution of possible input states must satisfy a particular property called ‘local decoupling’ (see Appendix C2 of their paper [1]). One particularly simple choice that will work for our 2D IDQNN is the following choice of three inputs, \(x=0,1,2\) (in the paper a different choice is used, but the result will be the same).

If \(x=0\), all input qubits are prepared in the \(\vert + \rangle\) state. If \(x=1\), all qubits on the ‘even diagonals’ of the lattice are prepared in \(\vert + \rangle\), the remaining are prepared in \(\vert 0 \rangle\). If \(x=2\), all qubits on the ‘odd diagonals’ of the lattice are prepared in \(\vert + \rangle\), the remaining are prepared in \(\vert 0 \rangle\).

Pictorially, the choice looks like this.

If the input is 0, we already know what happens; this is just the IDQNN described in the previous sections. If the input is 1 or 2, things get very simple. Note that the CZ gate is symmetric, and can be written as

Thus, if a CZ gate acts on the state \(\vert 0 \rangle\) on either side, the effect is that it becomes the identity. Since every CZ gate hits a qubit in the \(\vert 0 \rangle\) state for these inputs, we can actually remove them all. For example, the input \(x=1\) actually just corresponds to an unentangled product state:

By performing mid-circuit measurements and resetting qubits, we can easily reproduce the statistics for the inputs \(x=1,2\). For example, for \(x=1\), the circuit looks as follows (we have removed the rotation gates for the qubits prepared in \(\vert 0 \rangle\) since this results in a global phase only).

The authors argue that the conditional distribution \(p(\boldsymbol{y}|x)\) should also be considered hard to sample from classically, since the input \(x=0\) corresponds to the case of the ‘no input’ IDQNN of the previous sections, for which we have already argued hardness. For the inputs \(x=1\) and \(x=2\), however, the resulting distribution has an efficient classical simulation since it corresponds to measurements made on unentangled single qubits.

The necessity of prior knowledge

The first of these differences concerns the ‘prior knowledge’ that needs to be assumed in order to prove the result. Notice that, if we were given the data \({(x, \boldsymbol{y})}\) but told nothing else, we would not have known how to infer the parameters, nor how to produce new samples once these parameters were known, since these both required knowledge of the circuit. That is, precise knowledge of the circuit structures that produced the data was necessary in order to learn. In reality, such a precise form of the ground truth distribution is not known and models have to be learnt with vastly less prior knowledge. In their current form, these techniques therefore only appear useful for tasks related to quantum circuit tomography, where such knowledge is part of the problem description.

Learning from simple statistics

The second difference concerns how the parameters were learned. The parameters of modern classical generative models must be learned by an iterative process (often gradient descent) that extracts their values from complex, multidimensional correlations that are present in the statistics of the training data. For example, the parameters of convolutional filters in image models are adjusted to capture highly non-linear correlations, such as how edges, textures, and object parts co-occur across different spatial locations. In the quantum setup, although the distribution for the input \(x=0\) is undoubtedly complex, the data that is used for learning comes from the much simpler product distributions in which there are no correlations between bits.

As an illustrative comparison, imagine a large classical generative model (such as a diffusion model or a transformer) with parameters \(\theta\) and corresponding output distribution \(p(\boldsymbol{y})\). Suppose we want to learn the parameters \(\theta\) from data. To do this we construct a conditional distribution \(p(\boldsymbol{y}|x)\) which does the following:

• For \(x=0\), the model samples the generative model distribution \(p(\boldsymbol{y})\)

• For \(x=1\), \(\boldsymbol{y}\) just returns the parameters \(\theta\)

Obviously, we can learn the parameters of the model from \(p(\boldsymbol{y}|x)\): we just look at the data for \(x=1\) and read them off directly from \(\boldsymbol{y}\). Our quantum example is not dramatically different from this, since for the inputs \(x=1,2\) we have a simple method to read off the parameters from the statistics (single-qubit tomography), and this method is known beforehand rather than being learned from the data. In effect, we have set up the problem so that inferring parameters is straightforward for some inputs, whilst sampling is hard for others, and this process of learning is very different from the complex process that occurs in modern neural networks. We note that the specific example in the paper is more involved than this, and uses a higher dimensional lattice and a different set of inputs, but the strategy is the same: for each parameter, there is a reasonable fraction of the inputs that leaves the relevant qubit unentangled from the rest, and single-qubit statistics reveals the desired value.

What can lead us to genuine usefulness?

In order to uncover genuine usefulness in quantum machine learning we therefore need to move to scenarios that mirror the assumptions of realistic learning problems. If the flipside of this is that proving complexity theoretic separations becomes seemingly impossible, then perhaps they are not the right goals to be pursuing [3]? A more fruitful direction may be to instead look for other tools to evaluate the performance of quantum models. Although this means waving goodbye to computational complexity theory, this freedom just might be the fresh perspective we need to uncover genuinely useful quantum machine learning algorithms.