Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy

Abstract

Instantaneous quantum polynomial time (IQP) is a model of (probably) non-universal quantum computation. Since it has been proven that IQP circuits are unlikely to be simulated classically up to a multiplicative error and an error in the $l_1$ norm, IQP is considered as one of the promising classes that demonstrates quantum supremacy. Although IQP circuits can be realized more easily than a universal quantum computer, demonstrating quantum supremacy is still difficult. It is therefore desired to find subclasses of IQP that are easy to implement. In this paper, by imposing some restrictions on IQP, we propose ancilla-driven IQP (ADIQP) as the subclass of commuting quantum computation suitable for many experimental settings. We show that even though ADIQP circuits are strictly weaker than IQP circuits in a sense, they are also hard to simulate classically up to a multiplicative error and an error in the $l_1$ norm. Moreover, the properties of ADIQP make it easy to investigate the verifiability of ADIQP circuits and the difficulties in realizing ADIQP circuits.

6 pages, 4 figures

References in corpus (21)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Good Quantum Error-Correcting Codes Exist
• Multiple Particle Interference and Quantum Error Correction
• On the Power of One Bit of Quantum Information
• Experimental quantum computing without entanglement
• Boson Sampling on a Photonic Chip
• Experimental Boson Sampling
• Experimental boson sampling in arbitrary integrated photonic circuits
• Photonic Boson Sampling in a Tunable Circuit
• Boson Sampling for Molecular Vibronic Spectra
• Boson Sampling from Gaussian States
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Experimental Scattershot Boson Sampling
• Verifiable measurement-only blind quantum computing with stabilizer testing
• Instantaneous Quantum Computation
• Quantum computations with atoms in optical lattices: marker qubits and molecular interactions
• On the hardness of classically simulating the one clean qubit model
• Ancilla-Driven Universal Quantum Computation
• The complexity of simulating constant-depth BosonSampling
• Fault-tolerant verifiable blind quantum computing with logical state remote preparation

Cited by in corpus (5)

• Verification of Many-Qubit States
• Review on Quantum Walk Computing: Theory, Implementation, and Application
• Verifying commuting quantum computations via fidelity estimation of weighted graph states
• Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
• Hardness of efficiently generating ground states in postselected quantum computation