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:1412.4131

Nonlocality in instantaneous quantum circuits

Joel J. Wallman, Emily Adlam

Published Dec 12, 2014• 2 citations
arXivHTMLPDF

Abstract

We show that families of Instantaneous Quantum Polynomial (IQP) circuits corresponding to nontrivial Bell tests exhibit nonlocality. However, we also prove that this nonlocality can only be demonstrated using post-selection or nonlinear processing of the measurement outcomes. Therefore if the output of a computation is encoded in the parity of the measurement outcomes, then families of IQP circuits whose full output distributions are hard to sample still only provide a computational advantage relative to locally causal theories under post-selection. Consequently, post-selection is a crucial technique for obtaining a computational advantage for IQP circuits (with respect to decision problems) and for demonstrating nonlocality within IQP circuits, suggesting a strong link between these phenomena.

DOI
10.48550/arxiv.1412.4131

Related papers

Continuous-Variable Instantaneous Quantum Computing is hard to sample

Tom Douce, Damian Markham, Elham Kashefi +5 more

We study the translation of a recently introduced complexity class, Instantaneous Quantum Computing, to the regime of Continuous Variables (CV). Following the existing proof for the case of Discrete Variables (DV), we prove that CV IQP circuits are hard to classically simulate by exploring the properties of post-selected CV IQP circuits.

Quantum Information and Measurement (QIM)•Jan 1, 2017•2 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

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

The Impact of Qubit Connectivity on Quantum Advantage in Noisy IQP Circuits

Leonardo Placidi, Enrico Rinaldi, Keisuke Fujii +1 more

Instantaneous Quantum Polynomial-time (IQP) circuits are a candidate for demonstrating near-term quantum advantage, as their sampling task is believed to be classically hard in the ideal theoretical setting under standard complexity-theoretic assumptions. In noisy implementations, however, this hardness can disappear once circuit depth exceeds a noise-dependent critical threshold. We show that qubit connectivity is a key parameter in this transition, since sparse architectures require additional routing to implement long-range interactions, thereby increasing compiled circuit depth. To make this explicit, we present a connectivity-aware analysis of compiled IQP circuits. For a fixed abstract IQP instance, different hardware connectivity graphs yield different compiled depths and thus different effective positions relative to the noisy-IQP simulatability boundary. We quantify this architecture-dependent shift using the compiled depth overhead and the corresponding simulatability margin. We combine analytic depth estimates for sparse geometries, including the two-dimensional grid, with native-gateset-aware compilation experiments across seven hardware-grounded experimental device models derived from publicly available topologies. To compare these device models under a unified empirical framework, we approximate the effective noise level primarily through reported two-qubit gate error rates. This lets us compare how much effective noise sparse and fully connected architectures can tolerate for the same position relative to the noisy-IQP simulatability boundary. Our results show that sparse connectivity requires a lower effective noise level to sustain the same margin relative to the noisy-IQP simulatability boundary, and they provide a quantitative framework for determining when compiled IQP experiments are likely to remain outside, or instead enter, the classically simulatable regime.

quant-pharXiv:2604.12635•Apr 15, 2026•0 citations

On safe post-selection for Bell nonlocality: Causal diagram approach

Paweł Błasiak, Ewa Borsuk, Marcin Markiewicz

Reasoning about Bell nonlocality from the correlations observed in post-selected data is always a matter of concern. This is because conditioning on the outcomes is a source of non-causal correlations, known as a selection bias, rising doubts whether the conclusion concerns the actual causal process or maybe it is just an effect of processing the data. Yet, even in the idealised case without detection inefficiencies, post-selection is an integral part of every experimental design, not least because it is a part of the entanglement generation process itself. In this paper we discuss a broad class of scenarios with post-selection on multiple spatially distributed outcomes. A simple criterion is worked out, called the all-but-one principle, showing when the conclusions about nonlocality from breaking Bell inequalities with post-selected data remain in force. Generality of this result, attained by adopting the high-level diagrammatic tools of causal inference, provides safe grounds for systematic reasoning based on the standard form of multipartite Bell inequalities in a wide array of entanglement generation schemes without worrying about the dangers of selection bias.

•Dec 14, 2020•4 citations

Computational Perspectives on Bell Inequalities and Many-body Quantum Correlations

Matty J. Hoban

The predictions of quantum mechanics cannot be resolved with a completely classical view of the world. In particular, the statistics of space-like separated \nmeasurements on entangled quantum systems violate a Bell inequality [Bell1964]. \nWe put forward a computational perspective on a broad class of Bell tests that study correlators, or the statistics of joint measurement outcomes. We associate \nparticular maps, or functions to particular theories. The violation of a Bell \ninequality then implies the ability to perform some functions, or computations \nthat classical, or more generally, local hidden variable (LHV) theories cannot. \nWe derive an in�finite class of Bell inequalities that establish a link to so-called "non-local games" [Cleve2004]. We then make the connection between \nRaussendorf and Briegel's formulation of Measurement-based Quantum Computing (MBQC) [Raussendorf2001], and these non-local games. Not only can we show that a quantum violation implies a computational advantage in this model, \nwe show that adaptive measurements are required to perform all quantum computations. \nFinally, we explore post-selection of data in Bell tests from both a practical and \nconceptual point-of-view, with particular consideration to so-called "loopholes". \nLoopholes allow LHV theories to simulate quantum correlations through post-selection. \nWe give a computational description of how loopholes can emerge in diff�erent post-selection scenarios. This motivates us to �find a form of post-selection \nthat does not lead to loopholes. Central again to this discussion is the \ndescription of LHV theories in terms of computations. \nInterestingly, quantum correlators can be made more "non-classical" with this \nloophole-free post-selection. This method of post-selection also can simulate \ninformation processing tasks, such as MBQC, that have time-like separated components. \nThis opens up new avenues for the study of time-like tasks studied \nwithin the space-like separated scenario of the Bell test.

•Apr 26, 2012•0 citations
We show that families of Instantaneous Quantum Polynomial (IQP) circuits corresponding to nontrivial Bell tests exhibit nonlocality. However, we also prove that this nonlocality can only be demonstrated using post-selection or nonlinear processing of the measurement outcomes. Therefore if the output of a computation is encoded in the parity of the measurement outcomes, then families of IQP circuits whose full output distributions are hard to sample still only provide a computational advantage relative to locally causal theories under post-selection. Consequently, post-selection is a crucial technique for obtaining a computational advantage for IQP circuits (with respect to decision problems) and for demonstrating nonlocality within IQP circuits, suggesting a strong link between these phenomena.
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) 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.
Instantaneous Quantum Polynomial-time (IQP) circuits are a candidate for demonstrating near-term quantum advantage, as their sampling task is believed to be classically hard in the ideal theoretical setting under standard complexity-theoretic assumptions. In noisy implementations, however, this hardness can disappear once circuit depth exceeds a noise-dependent critical threshold. We show that qubit connectivity is a key parameter in this transition, since sparse architectures require additional routing to implement long-range interactions, thereby increasing compiled circuit depth. To make this explicit, we present a connectivity-aware analysis of compiled IQP circuits. For a fixed abstract IQP instance, different hardware connectivity graphs yield different compiled depths and thus different effective positions relative to the noisy-IQP simulatability boundary. We quantify this architecture-dependent shift using the compiled depth overhead and the corresponding simulatability margin. We combine analytic depth estimates for sparse geometries, including the two-dimensional grid, with native-gateset-aware compilation experiments across seven hardware-grounded experimental device models derived from publicly available topologies. To compare these device models under a unified empirical framework, we approximate the effective noise level primarily through reported two-qubit gate error rates. This lets us compare how much effective noise sparse and fully connected architectures can tolerate for the same position relative to the noisy-IQP simulatability boundary. Our results show that sparse connectivity requires a lower effective noise level to sustain the same margin relative to the noisy-IQP simulatability boundary, and they provide a quantitative framework for determining when compiled IQP experiments are likely to remain outside, or instead enter, the classically simulatable regime.
Reasoning about Bell nonlocality from the correlations observed in post-selected data is always a matter of concern. This is because conditioning on the outcomes is a source of non-causal correlations, known as a selection bias, rising doubts whether the conclusion concerns the actual causal process or maybe it is just an effect of processing the data. Yet, even in the idealised case without detection inefficiencies, post-selection is an integral part of every experimental design, not least because it is a part of the entanglement generation process itself. In this paper we discuss a broad class of scenarios with post-selection on multiple spatially distributed outcomes. A simple criterion is worked out, called the all-but-one principle, showing when the conclusions about nonlocality from breaking Bell inequalities with post-selected data remain in force. Generality of this result, attained by adopting the high-level diagrammatic tools of causal inference, provides safe grounds for systematic reasoning based on the standard form of multipartite Bell inequalities in a wide array of entanglement generation schemes without worrying about the dangers of selection bias.
The predictions of quantum mechanics cannot be resolved with a completely classical view of the world. In particular, the statistics of space-like separated \nmeasurements on entangled quantum systems violate a Bell inequality [Bell1964]. \nWe put forward a computational perspective on a broad class of Bell tests that study correlators, or the statistics of joint measurement outcomes. We associate \nparticular maps, or functions to particular theories. The violation of a Bell \ninequality then implies the ability to perform some functions, or computations \nthat classical, or more generally, local hidden variable (LHV) theories cannot. \nWe derive an in�finite class of Bell inequalities that establish a link to so-called "non-local games" [Cleve2004]. We then make the connection between \nRaussendorf and Briegel's formulation of Measurement-based Quantum Computing (MBQC) [Raussendorf2001], and these non-local games. Not only can we show that a quantum violation implies a computational advantage in this model, \nwe show that adaptive measurements are required to perform all quantum computations. \nFinally, we explore post-selection of data in Bell tests from both a practical and \nconceptual point-of-view, with particular consideration to so-called "loopholes". \nLoopholes allow LHV theories to simulate quantum correlations through post-selection. \nWe give a computational description of how loopholes can emerge in diff�erent post-selection scenarios. This motivates us to �find a form of post-selection \nthat does not lead to loopholes. Central again to this discussion is the \ndescription of LHV theories in terms of computations. \nInterestingly, quantum correlators can be made more "non-classical" with this \nloophole-free post-selection. This method of post-selection also can simulate \ninformation processing tasks, such as MBQC, that have time-like separated components. \nThis opens up new avenues for the study of time-like tasks studied \nwithin the space-like separated scenario of the Bell test.