Instantaneous quantum polynomial

“… although they are not the preferred problem of computer scientists, integrals of functions over many variables have been extensively studied with no known efficient algorithms known for arbitrary integrals.” - Arrazola et al. [28] on the applications of IQP.

Like boson sampling and Gaussian boson sampling before it, the instantaneous quantum polynomial (IQP) protocol is a restricted, non-universal model of quantum computation, designed to implement a computation that is classically intractable and verifiable by a remote adjudicator.

First introduced by [29] in the discrete variable qubit model, the scheme, due to its use of a non-universal gate set, is designed to scale in polynomial time. In particular, IQP circuits are defined as follows:

  1. there are \(N\) inputs in state \(\ket{0}\) acted on by Hadamard gates;
  2. the resulting computation is diagonal in the computational basis by randomly selecting from the set \(U=\{R(\pi/4),\sqrt{CZ}\}\);
  3. The output qubits are measured in the Pauli-X basis.

Note

Since all gates are diagonal in the computational basis, they all commute - therefore they can be applied in any temporal order. This is the origin of the term ‘instantaneous’ in IQP.

Efficient classically sampling the resulting probability distribution \(H^{\otimes N}UH^{\otimes N}\ket{0}^{\otimes N}\) - even approximately [30] or in the presence of noise [31] - has been shown to be #P-hard, and would result in the collapse of the polynomial hierarchy to the third level [32][33].

Unlike boson sampling and Gaussian boson sampling, however, the IQP protocol was not constructed with quantum linear optics in mind. Nevertheless, the IQP model was recently extended to the CV formulation of quantum computation [34], taking advantage of the ability to efficiently prepare large resource states, and the higher efficiencies afforded by homodyne detection. Furthermore, the computational complexity results of the discrete-variable case apply equally to the so-called CV-IQP model, assuming a specific input squeezing parameter dependent on the circuit size.

Moreover, the resulting probability distributions have been shown to be given by integrals of oscillating functions in large dimensions, which are belived to be intractable to compute by classical methods. This leads to the result that, even in the case of finite squeezing effects and reduced measurement precision, approximate sampling from the output CV-IQP model remains classically intractable [34][28].

CV implementation

The CV-IQP model is defined as follows:

  1. inputs are squeezed momentum states \(\ket{z}\), where \(z=r\in\mathbb{R}\) and \(r<0\) - these are implemented using Sgate;
  2. the unitary transformation is diagonal in the \(\hat{x}\) quadrature basis, by randomly selecting from the set of gates \(U=\{Z(p),CZ(s),V(\gamma)\}\) (available respectively as Zgate, CZgate, and Vgate);
  3. and finally, homodyne measurements are performed on all modes in the \(\hat{p}\) quadrature.

A circuit diagram of a 4 mode IQP circuit is given below.

../_images/IQP.svg

Blackbird code

The 4 mode IQP circuit displayed above, with gate parameters chosen randomly, can be implemented using the Blackbird quantum circuit language:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
# prepare the input squeezed states
S = Sgate(-1)
S | q[0]
S | q[1]
S | q[2]
S | q[3]

# gates diagonal in the x quadrature
CZgate(0.5719) | (q[0], q[1])
Vgate(-1.9782) | q[2]
Zgate(2.0603)  | q[3]
Zgate(-0.7804) | q[0]
Zgate(0.8578)  | q[2]
CZgate(1.321)  | (q[1], q[2])
Zgate(0.473)   | q[3]
CZgate(0.9946) | (q[0], q[3])
Zgate(0.1223)  | q[3]
Vgate(0.6157)  | q[0]
Vgate(0.3110)  | q[1]
Zgate(-1.243)  | q[2]

In the above circuit, the homodyne measurements have been excluded to allow for analysis of the full quantum state; however these can be included using MeasureHomodyne.

Note

A fully functional Strawberry Fields simulation containing the above Blackbird code is included at examples/IQP.py.