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:1912.06336 · Quantum

Additive-error fine-grained quantum supremacy

Tomoyuki Morimae, Suguru Tamaki

Published Sep 24, 2020• 4 citations
arXivHTMLPDF

Abstract

It is known that several sub-universal quantum computing models, such as the IQP model, the Boson sampling model, the one-clean qubit model, and the random circuit model, cannot be classically simulated in polynomial time under certain conjectures in classical complexity theory. Recently, these results have been improved to ``fine-grained" versions where even exponential-time classical simulations are excluded assuming certain classical fine-grained complexity conjectures. All these fine-grained results are, however, about the hardness of strong simulations or multiplicative-error sampling. It was open whether any fine-grained quantum supremacy result can be shown for a more realistic setup, namely, additive-error sampling. In this paper, we show the additive-error fine-grained quantum supremacy (under certain complexity assumptions). As examples, we consider the IQP model, a mixture of the IQP model and log-depth Boolean circuits, and Clifford+ T circuits. Similar results should hold for other sub-universal models.

DOI
10.22331/q-2020-09-24-329

Related papers

Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths

Hayakawa, Ryu, Tomoyuki Morimae, Suguru Tamaki

Fine-grained quantum supremacy is a study of proving (nearly) tight time lower bounds for classical simulations of quantum computing under "fine-grained complexity" assumptions. We show that under conjectures on Orthogonal Vectors (OV), 3-SUM, All-Pairs Shortest Paths (APSP) and their variants, strong and weak classical simulations of quantum computing are impossible in certain exponential time with respect to the number of qubits. Those conjectures are widely used in classical fine-grained complexity theory in which polynomial time hardness is conjectured. All previous results of fine-grained quantum supremacy are based on ETH, SETH, or their variants that are conjectures for SAT in which exponential time hardness is conjectured. We show that there exist quantum circuits which cannot be classically simulated in certain exponential time with respect to the number of qubits first by considering a Quantum Random Access Memory (QRAM) based quantum computing model and next by considering a non-QRAM model quantum computation. In the case of the QRAM model, the size of quantum circuits is linear with respect to the number of qubits and in the case of the non-QRAM model, the size of the quantum circuits is exponential with respect to the number of qubits but the results are still non-trivial.

arXiv:1902.08382•IEICE Technical Report; IEICE Tech. Rep.•Feb 22, 2019•1 citation

Fine-grained quantum computational supremacy

Tomoyuki Morimae, Suguru Tamaki

(pp1089-1115) Tomoyuki Morimae and Suguru Tamaki doi: https://doi.org/10.26421/QIC19.13-14-2 Abstracts: Output probability distributions of several sub-universal quantum computing models cannot be classically efficiently sampled unless some unlikely consequences occur in classical complexity theory, such as the collapse of the polynomial-time hierarchy. These results, so called quantum supremacy, however, do not rule out possibilities of super-polynomial-time classical simulations. In this paper, we study ``fine-grained" version of quantum supremacy that excludes some exponential-time classical simulations. First, we focus on two sub-universal models, namely, the one-clean-qubit model (or the DQC1 model) and the HC1Q model. Assuming certain conjectures in fine-grained complexity theory, we show that for any a>0 output probability distributions of these models cannot be classically sampled within a constant multiplicative error and in 2^{(1-a)N+o(N)} time, where N is the number of qubits. Next, we consider universal quantum computing. For example, we consider quantum computing over Clifford and T gates, and show that under another fine-grained complexity conjecture, output probability distributions of Clifford-T quantum computing cannot be classically sampled in 2^{o(t)} time within a constant multiplicative error, where t is the number of T gates.

arXiv:1901.01637•Quantum Information and Computation•Nov 1, 2019•11 citations

Depth-scaling fine-grained quantum supremacy based on SETH and qubit-scaling fine-grained quantum supremacy based on Orthogonal Vectors and 3-SUM.

Tomoyuki Morimae, Suguru Tamaki

We first show that under SETH and its variant, strong and weak classical simulations of quantum computing are impossible in certain double-exponential time of the circuit depth. We next show that under Orthogonal Vectors, 3-SUM, and their variants, strong and weak classical simulations of quantum computing are impossible in certain exponential time of the number of qubits.

•Feb 22, 2019•0 citations

Fine-grained analysis and improved robustness of quantum supremacy for random circuit sampling

Y. Kondo, Ryuhei Mori, Ramis Movassagh

We prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that estimating the output probabilities of random quantum circuits to within $\exp(-\Omega(m\log m))$ additive error is hard for any classical computer, where $m$ is the number of gates in the quantum computation. More precisely, we show that the above problem is $\#\mathsf{P}$-hard under $\mathsf{BPP}^{\mathsf{NP}}$ reduction. In the recent experiments, the quantum circuit has $n-$qubits and the architecture is a two-dimensional grid of size $\sqrt{n}\times\sqrt{n}$. Indeed for constant depth circuits estimating the output probabilities to within $2^{-\Omega(n\log{n})}$ is hard, and for circuits of depth $\sqrt{n}$, for which the anti-concentration property holds, estimating the output probabilities to within $2^{-\Omega(n^{3/2}\log n)}$ is hard. We prove these results from first principles and do not use the standard techniques such as the Berlekamp--Welch algorithm, the usual Paturi's lemma, and Rakhmanov's result.

•Feb 3, 2021•5 citations

How many qubits are needed for quantum computational supremacy?

Alexander M. Dalzell, Aram W. Harrow, Dax Enshan Koh +1 more

Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, typically require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy ( P H ) does not collapse, a stronger version of the statement that P ≠ N P , which leads to the conclusion that any classical simulation of certain families of quantum circuits requires time scaling worse than any polynomial in the size of the circuits. However, the asymptotic nature of this conclusion prevents us from calculating exactly how many qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers. We refine these quantum computational supremacy arguments and perform such a calculation by imposing fine-grained versions of the non-collapse conjecture. Our first two conjectures poly3-NSETH( a ) and per-int-NSETH( b ) take specific classical counting problems related to the number of zeros of a degree-3 polynomial in n variables over F 2 or the permanent of an n × n integer-valued matrix, and assert that any non-deterministic algorithm that solves them requires 2 c n time steps, where c ∈ { a , b } . A third conjecture poly3-ave-SBSETH( a ′ ) asserts a similar statement about average-case algorithms living in the exponential-time version of the complexity class S B P . We analyze evidence for these conjectures and argue that they are plausible when a = 1 / 2 , b = 0.999 and a ′ = 1 / 2 .Imposing poly3-NSETH(1/2) and per-int-NSETH(0.999), and assuming that the runtime of a hypothetical quantum circuit simulation algorithm would scale linearly with the number of gates/constraints/optical elements, we conclude that Instantaneous Quantum Polynomial-Time (IQP) circuits with 208 qubits and 500 gates, Quantum Approximate Optimization Algorithm (QAOA) circuits with 420 qubits and 500 constraints and boson sampling circuits (i.e. linear optical networks) with 98 photons and 500 optical elements are large enough for the task of producing samples from their output distributions up to constant multiplicative error to be intractable on current technology. Imposing poly3-ave-SBSETH(1/2), we additionally rule out simulations with constant additive error for IQP and QAOA circuits of the same size. Without the assumption of linearly increasing simulation time, we can make analogous statements for circuits with slightly fewer qubits but requiring 10 4 to 10 7 gates.

arXiv:1805.05224•Quantum•May 11, 2020•89 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
It is known that several sub-universal quantum computing models, such as the IQP model, the Boson sampling model, the one-clean qubit model, and the random circuit model, cannot be classically simulated in polynomial time under certain conjectures in classical complexity theory. Recently, these results have been improved to ``fine-grained" versions where even exponential-time classical simulations are excluded assuming certain classical fine-grained complexity conjectures. All these fine-grained results are, however, about the hardness of strong simulations or multiplicative-error sampling. It was open whether any fine-grained quantum supremacy result can be shown for a more realistic setup, namely, additive-error sampling. In this paper, we show the additive-error fine-grained quantum supremacy (under certain complexity assumptions). As examples, we consider the IQP model, a mixture of the IQP model and log-depth Boolean circuits, and Clifford+ T circuits. Similar results should hold for other sub-universal models.
Fine-grained quantum supremacy is a study of proving (nearly) tight time lower bounds for classical simulations of quantum computing under "fine-grained complexity" assumptions. We show that under conjectures on Orthogonal Vectors (OV), 3-SUM, All-Pairs Shortest Paths (APSP) and their variants, strong and weak classical simulations of quantum computing are impossible in certain exponential time with respect to the number of qubits. Those conjectures are widely used in classical fine-grained complexity theory in which polynomial time hardness is conjectured. All previous results of fine-grained quantum supremacy are based on ETH, SETH, or their variants that are conjectures for SAT in which exponential time hardness is conjectured. We show that there exist quantum circuits which cannot be classically simulated in certain exponential time with respect to the number of qubits first by considering a Quantum Random Access Memory (QRAM) based quantum computing model and next by considering a non-QRAM model quantum computation. In the case of the QRAM model, the size of quantum circuits is linear with respect to the number of qubits and in the case of the non-QRAM model, the size of the quantum circuits is exponential with respect to the number of qubits but the results are still non-trivial.
(pp1089-1115) Tomoyuki Morimae and Suguru Tamaki doi: https://doi.org/10.26421/QIC19.13-14-2 Abstracts: Output probability distributions of several sub-universal quantum computing models cannot be classically efficiently sampled unless some unlikely consequences occur in classical complexity theory, such as the collapse of the polynomial-time hierarchy. These results, so called quantum supremacy, however, do not rule out possibilities of super-polynomial-time classical simulations. In this paper, we study ``fine-grained" version of quantum supremacy that excludes some exponential-time classical simulations. First, we focus on two sub-universal models, namely, the one-clean-qubit model (or the DQC1 model) and the HC1Q model. Assuming certain conjectures in fine-grained complexity theory, we show that for any a>0 output probability distributions of these models cannot be classically sampled within a constant multiplicative error and in 2^{(1-a)N+o(N)} time, where N is the number of qubits. Next, we consider universal quantum computing. For example, we consider quantum computing over Clifford and T gates, and show that under another fine-grained complexity conjecture, output probability distributions of Clifford-T quantum computing cannot be classically sampled in 2^{o(t)} time within a constant multiplicative error, where t is the number of T gates.
We prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that estimating the output probabilities of random quantum circuits to within exp⁡(−Ω(mlog⁡m))\exp(-\Omega(m\log m))exp(−Ω(mlogm)) additive error is hard for any classical computer, where mmm is the number of gates in the quantum computation. More precisely, we show that the above problem is #P\#\mathsf{P}#P-hard under BPPNP\mathsf{BPP}^{\mathsf{NP}}BPPNP reduction. In the recent experiments, the quantum circuit has n−n-n−qubits and the architecture is a two-dimensional grid of size n×n\sqrt{n}\times\sqrt{n}n​×n​. Indeed for constant depth circuits estimating the output probabilities to within 2−Ω(nlog⁡n)2^{-\Omega(n\log{n})}2−Ω(nlogn) is hard, and for circuits of depth n\sqrt{n}n​, for which the anti-concentration property holds, estimating the output probabilities to within 2−Ω(n3/2log⁡n)2^{-\Omega(n^{3/2}\log n)}2−Ω(n3/2logn) is hard. We prove these results from first principles and do not use the standard techniques such as the Berlekamp--Welch algorithm, the usual Paturi's lemma, and Rakhmanov's result.
Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, typically require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy ( P H ) does not collapse, a stronger version of the statement that P ≠ N P , which leads to the conclusion that any classical simulation of certain families of quantum circuits requires time scaling worse than any polynomial in the size of the circuits. However, the asymptotic nature of this conclusion prevents us from calculating exactly how many qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers. We refine these quantum computational supremacy arguments and perform such a calculation by imposing fine-grained versions of the non-collapse conjecture. Our first two conjectures poly3-NSETH( a ) and per-int-NSETH( b ) take specific classical counting problems related to the number of zeros of a degree-3 polynomial in n variables over F 2 or the permanent of an n × n integer-valued matrix, and assert that any non-deterministic algorithm that solves them requires 2 c n time steps, where c ∈ { a , b } . A third conjecture poly3-ave-SBSETH( a ′ ) asserts a similar statement about average-case algorithms living in the exponential-time version of the complexity class S B P . We analyze evidence for these conjectures and argue that they are plausible when a = 1 / 2 , b = 0.999 and a ′ = 1 / 2 .Imposing poly3-NSETH(1/2) and per-int-NSETH(0.999), and assuming that the runtime of a hypothetical quantum circuit simulation algorithm would scale linearly with the number of gates/constraints/optical elements, we conclude that Instantaneous Quantum Polynomial-Time (IQP) circuits with 208 qubits and 500 gates, Quantum Approximate Optimization Algorithm (QAOA) circuits with 420 qubits and 500 constraints and boson sampling circuits (i.e. linear optical networks) with 98 photons and 500 optical elements are large enough for the task of producing samples from their output distributions up to constant multiplicative error to be intractable on current technology. Imposing poly3-ave-SBSETH(1/2), we additionally rule out simulations with constant additive error for IQP and QAOA circuits of the same size. Without the assumption of linearly increasing simulation time, we can make analogous statements for circuits with slightly fewer qubits but requiring 10 4 to 10 7 gates.
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.