r"""
.. role:: html(raw)
:format: html
.. _iqp:
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 :math:`N` inputs in state :math:`\ket{0}` acted on by Hadamard gates;
2. the resulting computation is diagonal in the computational basis by randomly selecting from the
set :math:`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 :math:`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 :math:`\ket{z}`, where :math:`z=r\in\mathbb{R}` and
:math:`r<0` - these are implemented using :class:`~strawberryfields.ops.Sgate`;
2. the unitary transformation is diagonal in the :math:`\hat{x}` quadrature basis, by randomly
selecting from the set of gates :math:`U=\{Z(p),CZ(s),V(\gamma)\}` (available respectively as
:class:`~strawberryfields.ops.Zgate`, :class:`~strawberryfields.ops.CZgate`, and
:class:`~strawberryfields.ops.Vgate`);
3. and finally, homodyne measurements are performed on all modes in the :math:`\hat{p}` quadrature.
A circuit diagram of a 4 mode IQP circuit is given below.
.. image:: /tutorials/images/IQP.svg
:align: center
:width: 50%
:target: javascript:void(0);
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
# :class:`~strawberryfields.ops.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] J. M. Arrazola, P. Rebentrost, and C. Weedbrook. Quantum supremacy and high-dimensional integration.
# 2017. arXiv:1712.07288.
#
# .. [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] 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.