Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1611.00510 · Physical Review A

Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy

Yuki Takeuchi, Yasuhiro Takahashi

Published Dec 27, 2016• 6 citations
arXivHTMLPDF

Abstract

Instantaneous quantum polynomial time (IQP) is a model of (probably) nonuniversal 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.

DOI
10.1103/physreva.94.062336

Related papers

Achieving quantum supremacy with sparse and noisy commuting quantum computations

Michael J. Bremner, Ashley Montanaro, Dan J. Shepherd

The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here we study the power of IQP circuits in the presence of physically motivated constraints. First, we show that there is a family of sparse IQP circuits that can be implemented on a square lattice of n qubits in depth O(sqrt(n) log n), and which is likely hard to simulate classically. Next, we show that, if an arbitrarily small constant amount of noise is applied to each qubit at the end of any IQP circuit whose output probability distribution is sufficiently anticoncentrated, there is a polynomial-time classical algorithm that simulates sampling from the resulting distribution, up to constant accuracy in total variation distance. However, we show that purely classical error-correction techniques can be used to design IQP circuits which remain hard to simulate classically, even in the presence of arbitrary amounts of noise of this form. These results demonstrate the challenges faced by experiments designed to demonstrate quantum supremacy over classical computation, and how these challenges can be overcome.

arXiv:1610.01808•Quantum•Apr 25, 2017•191 citations

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth

Joel Rajakumar, James D. Watson, Yi-Kai Liu

Sampling from the output distributions of quantum computations comprising only commuting gates, known as instantaneous quantum polynomial (IQP) computations, is believed to be intractable for classical computers, and hence this task has become a leading candidate for testing the capabilities of quantum devices. Here we demonstrate that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, whose depth is greater than a critical O (1) threshold, the output distribution can be efficiently sampled by a classical computer. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit’s architecture, on anti-concentration properties, nor do we require Ω(log (n )) circuit depth. We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit. Our results suggest that quantum supremacy experiments based on IQP circuits may be more susceptible to classical simulation than previously thought. Furthermore, we show that the critical depth threshold of our algorithm is tight, and below this threshold there are noisy IQP circuits which are hard to sample from. Thus we demonstrate that noisy IQP circuits exhibit a phase transition in the computational complexity of sampling, as circuit depth is increased.

arXiv:2403.14607•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2025•7 citations

Commuting quantum circuits and complexity of Ising partition functions

Keisuke Fujii, Tomoyuki Morimae

Instantaneous quantum polynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal. Nevertheless, it has been shown that if there is a classical algorithm that can simulate IQP efficiently, the polynomial hierarchy collapses to the third level, which is highly implausible. However, the origin of the classical intractability is still less understood. Here we establish a relationship between IQP and computational complexity of calculating the imaginary-valued partition functions of Ising models. We apply the established relationship in two opposite directions. One direction is to find subclasses of IQP that are classically efficiently simulatable by using exact solvability of certain types of Ising models. Another direction is applying quantum computational complexity of IQP to investigate (im)possibility of efficient classical approximations of Ising partition functions with imaginary coupling constants. Specifically, we show that a multiplicative approximation of Ising partition functions is #P-hard for almost all imaginary coupling constants even on planar lattices of a bounded degree.

arXiv:1311.2128•New Journal of Physics•Feb 10, 2017•48 citations

Verifying commuting quantum computations via fidelity estimation of weighted graph states

Masahito Hayashi, Yuki Takeuchi

Abstract The instantaneous quantum polynomial time (IQP) model is one of promising models to demonstrate a quantum computational advantage over classical computers. If the IQP model can be efficiently simulated by a classical computer, an unlikely consequence in computer science can be obtained (under some unproven conjectures). In order to experimentally demonstrate the advantage using medium or large-scale IQP circuits, it is inevitable to efficiently verify whether the constructed IQP circuits faithfully work. There exist two types of IQP models, each of which is the sampling on hypergraph states or weighted graph states. For the first-type IQP model, polynomial-time verification protocols have already been proposed. In this paper, we propose verification protocols for the second-type IQP model. To this end, we propose polynomial-time fidelity estimation protocols of weighted graph states for each of the following four situations where a verifier can (i) choose any measurement basis and perform adaptive measurements, (ii) only choose restricted measurement bases and perform adaptive measurements, (iii) choose any measurement basis and only perform non-adaptive measurements, and (iv) only choose restricted measurement bases and only perform non-adaptive measurements. In all of our verification protocols, the verifier’s quantum operations are only single-qubit measurements. Since we assume no independent and identically distributed property on quantum states, our protocols work in any situation.

arXiv:1902.03369•New Journal of Physics•Aug 21, 2019•27 citations

Classically simulating intermediate-scale instantaneous quantum polynomial circuits through a random graph approach

Julien Codsi, John van de Wetering

Quantum advantage is a demonstration of a computation by a quantum computer that cannot be performed by the best classical computer in a reasonable time. A well-studied approach to demonstrating this on near-term quantum computers is to use random circuit sampling. It has been suggested that a good candidate for demonstrating quantum advantage with random circuit sampling is to use instantaneous quantum polynomial (IQP) circuits. These are quantum circuits where the unitary it implements is diagonal. In this paper, we introduce improved techniques for exactly classically simulating random IQP circuits. We find a simple algorithm to calculate an amplitude of an $n$-qubit IQP circuit with dense random two-qubit interactions in time $O(\frac{{log}^{2}n}{n}{2}^{n})$, which for sparse circuits (where each qubit interacts with $O(logn)$ other qubits) runs in $o({2}^{n}/\mathrm{poly}(n))$ for any given polynomial. Using a more complicated stabilizer decomposition approach we improve the algorithm for dense circuits to $O(\frac{{(logn)}^{4\ensuremath{-}\ensuremath{\beta}}}{{n}^{2\ensuremath{-}\ensuremath{\beta}}}{2}^{n})$ where $\ensuremath{\beta}\ensuremath{\approx}0.396$. We further discuss how our techniques also lead to improved simulation times for IQP circuits on restricted architectures. We benchmarked our main algorithm and found that we can simulate up to 50-qubit circuits in a couple of minutes on a laptop, with 68-qubit sparse circuits taking a couple of hours. We estimate dense 70-qubit circuits are in range for large computing clusters.

arXiv:2212.08609•Physical Review A•Jan 14, 2025•4 citations

Trainability and Mode Separation of Mixed IQP-QCBMs

Youngseok Lee, Hyunwoo Kim

Quantum circuit Born machines (QCBMs) based on instantaneous quantum polynomial-time (IQP) circuits are promising quantum generative models for their classical trainability. It is known that their ancilla-free form avoids barren plateaus under certain initializations, but remains non-universal. Although adding ancilla qubits raises the expressivity, whether the ancilla-extended model retains local trainability remains unknown. We propose the mixed IQP-QCBM, which generalizes the ancilla-extended circuit as a weighted mixture of ancilla-free IQP circuits, called branches. For a polynomial number of branches, we prove local barren-plateau avoidance from data-agnostic and, under certain assumptions, data-dependent initializations. We further show that the mixed IQP-QCBM can surpass the best ancilla-free IQP circuit only if its branches generate a number of distinct distributions. In particular, we focus on a behavior we call \emph{mode separation}, in which each branch captures a particular feature of the target. Mode separation is hard to attain from an initialization whose branches generate the same distribution: the gradients that would separate them are suppressed while the distributions they generate remain close. This motivates \emph{cluster initialization}, which assigns a different unsupervised data cluster to each branch and provides an initial degree of mode separation. Exact calculations on two 16-bit datasets support the barren-plateau and gradient-suppression claims. On four benchmarks, binary clusters, a two-dimensional Ising model, binarized MNIST, and a 484-spin glass, cluster initialization converges fastest and reaches the lowest mean test $\mathrm{MMD}^2$. We observe that, when achieving the lowest test $\mathrm{MMD}^2$, the mixed IQP-QCBM contains branches specialized to distinguishable data features such as blob patterns, magnetization sectors, or digit shapes.

quant-pharXiv:2607.27883•Jul 31, 2026•0 citations
Instantaneous quantum polynomial time (IQP) is a model of (probably) nonuniversal 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 l1{l}_{1}l1​ 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 l1{l}_{1}l1​ norm. Moreover, the properties of ADIQP make it easy to investigate the verifiability of ADIQP circuits and the difficulties in realizing ADIQP circuits.
The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here we study the power of IQP circuits in the presence of physically motivated constraints. First, we show that there is a family of sparse IQP circuits that can be implemented on a square lattice of n qubits in depth O(sqrt(n) log n), and which is likely hard to simulate classically. Next, we show that, if an arbitrarily small constant amount of noise is applied to each qubit at the end of any IQP circuit whose output probability distribution is sufficiently anticoncentrated, there is a polynomial-time classical algorithm that simulates sampling from the resulting distribution, up to constant accuracy in total variation distance. However, we show that purely classical error-correction techniques can be used to design IQP circuits which remain hard to simulate classically, even in the presence of arbitrary amounts of noise of this form. These results demonstrate the challenges faced by experiments designed to demonstrate quantum supremacy over classical computation, and how these challenges can be overcome.
Sampling from the output distributions of quantum computations comprising only commuting gates, known as instantaneous quantum polynomial (IQP) computations, is believed to be intractable for classical computers, and hence this task has become a leading candidate for testing the capabilities of quantum devices. Here we demonstrate that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, whose depth is greater than a critical O (1) threshold, the output distribution can be efficiently sampled by a classical computer. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit’s architecture, on anti-concentration properties, nor do we require Ω(log (n )) circuit depth. We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit. Our results suggest that quantum supremacy experiments based on IQP circuits may be more susceptible to classical simulation than previously thought. Furthermore, we show that the critical depth threshold of our algorithm is tight, and below this threshold there are noisy IQP circuits which are hard to sample from. Thus we demonstrate that noisy IQP circuits exhibit a phase transition in the computational complexity of sampling, as circuit depth is increased.
Instantaneous quantum polynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal. Nevertheless, it has been shown that if there is a classical algorithm that can simulate IQP efficiently, the polynomial hierarchy collapses to the third level, which is highly implausible. However, the origin of the classical intractability is still less understood. Here we establish a relationship between IQP and computational complexity of calculating the imaginary-valued partition functions of Ising models. We apply the established relationship in two opposite directions. One direction is to find subclasses of IQP that are classically efficiently simulatable by using exact solvability of certain types of Ising models. Another direction is applying quantum computational complexity of IQP to investigate (im)possibility of efficient classical approximations of Ising partition functions with imaginary coupling constants. Specifically, we show that a multiplicative approximation of Ising partition functions is #P-hard for almost all imaginary coupling constants even on planar lattices of a bounded degree.
Abstract The instantaneous quantum polynomial time (IQP) model is one of promising models to demonstrate a quantum computational advantage over classical computers. If the IQP model can be efficiently simulated by a classical computer, an unlikely consequence in computer science can be obtained (under some unproven conjectures). In order to experimentally demonstrate the advantage using medium or large-scale IQP circuits, it is inevitable to efficiently verify whether the constructed IQP circuits faithfully work. There exist two types of IQP models, each of which is the sampling on hypergraph states or weighted graph states. For the first-type IQP model, polynomial-time verification protocols have already been proposed. In this paper, we propose verification protocols for the second-type IQP model. To this end, we propose polynomial-time fidelity estimation protocols of weighted graph states for each of the following four situations where a verifier can (i) choose any measurement basis and perform adaptive measurements, (ii) only choose restricted measurement bases and perform adaptive measurements, (iii) choose any measurement basis and only perform non-adaptive measurements, and (iv) only choose restricted measurement bases and only perform non-adaptive measurements. In all of our verification protocols, the verifier’s quantum operations are only single-qubit measurements. Since we assume no independent and identically distributed property on quantum states, our protocols work in any situation.
Quantum advantage is a demonstration of a computation by a quantum computer that cannot be performed by the best classical computer in a reasonable time. A well-studied approach to demonstrating this on near-term quantum computers is to use random circuit sampling. It has been suggested that a good candidate for demonstrating quantum advantage with random circuit sampling is to use instantaneous quantum polynomial (IQP) circuits. These are quantum circuits where the unitary it implements is diagonal. In this paper, we introduce improved techniques for exactly classically simulating random IQP circuits. We find a simple algorithm to calculate an amplitude of an nnn-qubit IQP circuit with dense random two-qubit interactions in time O(log2nn2n)O(\frac{{log}^{2}n}{n}{2}^{n})O(nlog2n​2n), which for sparse circuits (where each qubit interacts with O(logn)O(logn)O(logn) other qubits) runs in o(2n/poly(n))o({2}^{n}/\mathrm{poly}(n))o(2n/poly(n)) for any given polynomial. Using a more complicated stabilizer decomposition approach we improve the algorithm for dense circuits to $O(\frac{{(logn)}^{4\ensuremath{-}\ensuremath{\beta}}}{{n}^{2\ensuremath{-}\ensuremath{\beta}}}{2}^{n})$ where $\ensuremath{\beta}\ensuremath{\approx}0.396$. We further discuss how our techniques also lead to improved simulation times for IQP circuits on restricted architectures. We benchmarked our main algorithm and found that we can simulate up to 50-qubit circuits in a couple of minutes on a laptop, with 68-qubit sparse circuits taking a couple of hours. We estimate dense 70-qubit circuits are in range for large computing clusters.
Quantum circuit Born machines (QCBMs) based on instantaneous quantum polynomial-time (IQP) circuits are promising quantum generative models for their classical trainability. It is known that their ancilla-free form avoids barren plateaus under certain initializations, but remains non-universal. Although adding ancilla qubits raises the expressivity, whether the ancilla-extended model retains local trainability remains unknown. We propose the mixed IQP-QCBM, which generalizes the ancilla-extended circuit as a weighted mixture of ancilla-free IQP circuits, called branches. For a polynomial number of branches, we prove local barren-plateau avoidance from data-agnostic and, under certain assumptions, data-dependent initializations. We further show that the mixed IQP-QCBM can surpass the best ancilla-free IQP circuit only if its branches generate a number of distinct distributions. In particular, we focus on a behavior we call \emph{mode separation}, in which each branch captures a particular feature of the target. Mode separation is hard to attain from an initialization whose branches generate the same distribution: the gradients that would separate them are suppressed while the distributions they generate remain close. This motivates \emph{cluster initialization}, which assigns a different unsupervised data cluster to each branch and provides an initial degree of mode separation. Exact calculations on two 16-bit datasets support the barren-plateau and gradient-suppression claims. On four benchmarks, binary clusters, a two-dimensional Ising model, binarized MNIST, and a 484-spin glass, cluster initialization converges fastest and reaches the lowest mean test MMD2\mathrm{MMD}^2MMD2. We observe that, when achieving the lowest test MMD2\mathrm{MMD}^2MMD2, the mixed IQP-QCBM contains branches specialized to distinguishable data features such as blob patterns, magnetization sectors, or digit shapes.