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:1902.03369 · New Journal of Physics

Verifying commuting quantum computations via fidelity estimation of weighted graph states

Masahito Hayashi, Yuki Takeuchi

Published Aug 21, 2019• 27 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/1367-2630/ab3d88

Related papers

Passive verification protocol for thermal graph states

Kazuki Akimoto, Shunji Tsuchiya, Ryosuke Yoshii +1 more

Graph states are entangled resource states for universal measurement-based quantum computation. Although matter qubits such as superconducting circuits and trapped ions are promising candidates to generate graph states, it is technologically hard to entangle a large number of them due to several types of noise. Since they must be sufficiently cooled to maintain their quantum properties, thermal noise is one of the major ones. In this paper, we show that, for any temperature $T$, the fidelity $\ensuremath{\langle}G|{\ensuremath{\rho}}_{T}|G\ensuremath{\rangle}$ between an ideal graph state $|G\ensuremath{\rangle}$ at zero temperature and a thermal graph state ${\ensuremath{\rho}}_{T}$, which is a graph state at temperature $T$, can be efficiently estimated by using only one measurement setting. A remarkable property of our protocol is that it is passive, while existing protocols are active, namely, they switch between at least two measurement settings. Since thermal noise is equivalent to an independent phase-flip error, our estimation protocol also works for that error. By generalizing our protocol to hypergraph states, we apply our protocol to the quantum-computational-supremacy demonstration with instantaneous quantum polynomial time circuits. Our results should make the characterization of entangled matter qubits extremely feasible under thermal noise.

arXiv:2202.10624•Physical Review A•Jul 5, 2022•2 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

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

Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy

Yuki Takeuchi, Yasuhiro Takahashi

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.

arXiv:1611.00510•Physical Review A•Dec 27, 2016•6 citations

Shallow instantaneous quantum polynomial-time circuits for generative modeling on noisy intermediate-scale quantum hardware

Oriol Balló-Gimbernat, Marcos Arroyo-Sánchez, Paula García-Molina +2 more

Generative modeling is one of the most promising applications of quantum machine learning, yet training and deploying Quantum Generative Models (QGMs) on near-term hardware remains effectively intractable due to prohibitive gradient estimation and implementation costs. We propose a resource-efficient approach based on shallow Instantaneous Quantum Polynomial-time (IQP) circuits that circumvents these bottlenecks by leveraging efficient classical training while retaining the guarantee of sampling hardness. To validate this approach, we formalize graph generation as a hierarchy of physical correlations, allowing us to map abstract data features, such as edge density and bipartiteness, directly to the quantum observables required to learn them. We validate our protocol through demonstrations both on real hardware (from $28$ to $153$ qubits) and simulations ($28$ qubits). Results show that while global structural features exhibit significant degradation beyond $91$ qubits, our models achieve high-precision reproduction of local correlations, even up to $153$ qubits. These findings establish shallow IQP circuits as a robust, scalable candidate for generative tasks on current Noisy Intermediate-Scale Quantum (NISQ) devices.

quant-pharXiv:2511.05267•Physical Review A•Nov 10, 2025•0 citations

Generative Graph Modeling on NISQ Computers

Oriol Balló-Gimbernat, Marcos Arroyo-Sánchez

Quantum generative models offer an inherently efficient sampling procedure, yet their training on quantum hardware is often a bottleneck. Parametrized Instantaneous Quantum Polynomial-time (IQP) circuits present a promising approach combining classical training with single-shot measurements for sample generation. However, its practical viability on Noisy Intermediate-Scale Quantum (NISQ) hardware remains an open question. In this work, we provide the first large-scale experimental validation of this method for learning graph distributions with both local (edge probabilities) and global (‘2-colorability’) constraints. While our graph encoding requires a number of qubits that scales quadratically with node count, our experiments, ranging from 28 to 153 qubits, demonstrate the approach's capabilities and limitations. For instance, a 153-qubit model successfully learned sparse ErdősRényi graphs with an average edge probability error below two percentage points. In contrast, learning the global property of bipartiteness proved more challenging and sensitive to noise, achieving 25.78 % accuracy for 18-node sparse instances. These results validate parametrized IQP circuits as a practical tool for generative modeling on near-term devices, while clearly delineating the critical challenges that must be addressed for future progress.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations
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.
Graph states are entangled resource states for universal measurement-based quantum computation. Although matter qubits such as superconducting circuits and trapped ions are promising candidates to generate graph states, it is technologically hard to entangle a large number of them due to several types of noise. Since they must be sufficiently cooled to maintain their quantum properties, thermal noise is one of the major ones. In this paper, we show that, for any temperature TTT, the fidelity $\ensuremath{\langle}G|{\ensuremath{\rho}}_{T}|G\ensuremath{\rangle}$ between an ideal graph state $|G\ensuremath{\rangle}$ at zero temperature and a thermal graph state ${\ensuremath{\rho}}_{T}$, which is a graph state at temperature TTT, can be efficiently estimated by using only one measurement setting. A remarkable property of our protocol is that it is passive, while existing protocols are active, namely, they switch between at least two measurement settings. Since thermal noise is equivalent to an independent phase-flip error, our estimation protocol also works for that error. By generalizing our protocol to hypergraph states, we apply our protocol to the quantum-computational-supremacy demonstration with instantaneous quantum polynomial time circuits. Our results should make the characterization of entangled matter qubits extremely feasible under thermal noise.
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.
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.
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.
Generative modeling is one of the most promising applications of quantum machine learning, yet training and deploying Quantum Generative Models (QGMs) on near-term hardware remains effectively intractable due to prohibitive gradient estimation and implementation costs. We propose a resource-efficient approach based on shallow Instantaneous Quantum Polynomial-time (IQP) circuits that circumvents these bottlenecks by leveraging efficient classical training while retaining the guarantee of sampling hardness. To validate this approach, we formalize graph generation as a hierarchy of physical correlations, allowing us to map abstract data features, such as edge density and bipartiteness, directly to the quantum observables required to learn them. We validate our protocol through demonstrations both on real hardware (from 282828 to 153153153 qubits) and simulations (282828 qubits). Results show that while global structural features exhibit significant degradation beyond 919191 qubits, our models achieve high-precision reproduction of local correlations, even up to 153153153 qubits. These findings establish shallow IQP circuits as a robust, scalable candidate for generative tasks on current Noisy Intermediate-Scale Quantum (NISQ) devices.
Quantum generative models offer an inherently efficient sampling procedure, yet their training on quantum hardware is often a bottleneck. Parametrized Instantaneous Quantum Polynomial-time (IQP) circuits present a promising approach combining classical training with single-shot measurements for sample generation. However, its practical viability on Noisy Intermediate-Scale Quantum (NISQ) hardware remains an open question. In this work, we provide the first large-scale experimental validation of this method for learning graph distributions with both local (edge probabilities) and global (‘2-colorability’) constraints. While our graph encoding requires a number of qubits that scales quadratically with node count, our experiments, ranging from 28 to 153 qubits, demonstrate the approach's capabilities and limitations. For instance, a 153-qubit model successfully learned sparse ErdősRényi graphs with an average edge probability error below two percentage points. In contrast, learning the global property of bipartiteness proved more challenging and sensitive to noise, achieving 25.78 % accuracy for 18-node sparse instances. These results validate parametrized IQP circuits as a practical tool for generative modeling on near-term devices, while clearly delineating the critical challenges that must be addressed for future progress.