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. [1] 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 [2] in the discrete variable qubit model, the protocol is devised with a two-party classical communication channel in mind; here, Alice designs a classically intractable problem with a ‘hidden variable’ she can use to verify the result. Bob then runs the IQP scheme with Alice’s input; the scheme, due to its use of a non-universal gate set, is designed to scale in polynomial time. Finally, Alice verifies that Bob has achieved quantum supremacy, by considering the time taken to receive the result and using her hidden knowledge of the problem set.

First introduced by [2] 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 [3] or in the presence of noise [4] - has been shown to be #P-hard, and would result in the collapse of the polynomial hierarchy to the third level [5][6].

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 [7], 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 [1][7].

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.

Code

The 4 mode IQP circuit displayed above, with gate parameters chosen randomly, can be implemented using Strawberry Fields:

import strawberryfields as sf
from strawberryfields.ops import *

iqp_circuit = sf.Program(4)

with iqp_circuit.context as q:
    # 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.

Since non-Gaussian cubic phase gates are used in the above circuit, we must run it on a Fock backend. Here, we choose the Fock backend with a cutoff dimension of 5.

# initialize engine
eng = sf.Engine(backend="fock", backend_options={"cutoff_dim": 5})

# run the engine
results = eng.run(iqp_circuit)

References

1(1,2)

J. M. Arrazola, P. Rebentrost, and C. Weedbrook. Quantum supremacy and high-dimensional integration. 2017. arXiv:1712.07288.

2(1,2)

Dan Shepherd and Michael J. Bremner. Temporally unstructured quantum computation. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 465(2105):1413–1439, 2009. doi:10.1098/rspa.2008.0443.

3

Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Physical Review Letters, 2016. doi:10.1103/PhysRevLett.117.080501.

4

Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum, 1:8, 2017. doi:10.22331/q-2017-04-25-8.

5

A. P. Lund, Michael J. Bremner, and T. C. Ralph. Quantum sampling problems, BosonSampling and quantum supremacy. npj Quantum Information, 2017. arXiv:1702.03061, doi:10.1038/s41534-017-0018-2.

6

Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 2010. arXiv:1005.1407, doi:10.1098/rspa.2010.0301.

7(1,2)

T. Douce, D. Markham, E. Kashefi, E. Diamanti, T. Coudreau, P. Milman, P. van Loock, and G. Ferrini. Continuous-variable instantaneous quantum computing is hard to sample. Physical Review Letters, 2017. arXiv:1607.07605, doi:10.1103/PhysRevLett.118.070503.

demos/run_iqp

 

Download Python script

 

Download Notebook