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:quant-ph/9910033 · Information and Computation

Almost-Everywhere Superiority for Quantum Polynomial Time

Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand

Published Jun 1, 2002• 19 citations
arXivHTMLPDF
DOI
10.1006/inco.2001.3110

Related papers

Polynomial time quantum computation with advice

Harumichi Nishimura, Tomoyuki Yamakami

arXiv:quant-ph/0305100•Information Processing Letters•Mar 20, 2004•54 citations

Almost-Everywhere Superiority for Quantum Polynomial-Time Languages

Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand

We prove that there are languages for which polynomial-time quantum machines are exponentially faster than each classical machine almost everywhere.

•Aug 1, 2002•1 citation

Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms

N Nikhil Bansal, M. (Makrand) Sinha, Ronald de Wolf

The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if true, would imply that the acceptance probability of every $d$-query quantum algorithm can be well-approximated almost everywhere (i.e., on almost all inputs) by a $\mathrm{poly}(d)$-query classical algorithm. We prove a special case of the conjecture: in every completely bounded degree-$d$ block-multilinear form with constant variance, there always exists a variable with influence at least $1/\mathrm{poly}(d)$. In a certain sense, such polynomials characterize the acceptance probability of quantum query algorithms, as shown by Arunachalam, Briët and Palazuelos (SICOMP '19). As a corollary we obtain efficient classical almost-everywhere simulation for a particular class of quantum algorithms that includes for instance $k$-fold Forrelation. Our main technical result relies on connections to free probability theory.

arXiv:2203.00212•Leibniz international proceedings in informatics•Jan 1, 2022•10 citations

Recent Developments in Quantum Algorithms and Complexity

Andris Ambainis

Lecture notes in computer science•Jan 1, 2014•1 citation

Aaronson-Ambainis Conjecture Is True For Random Restrictions

Sreejata Kishor Bhattacharya

In an attempt to show that the acceptance probability of a quantum query algorithm making $q$ queries can be well-approximated almost everywhere by a classical decision tree of depth $\leq \text{poly}(q)$, Aaronson and Ambainis proposed the following conjecture: let $f: \{ \pm 1\}^n \rightarrow [0,1]$ be a degree $d$ polynomial with variance $\geq ε$. Then, there exists a coordinate of $f$ with influence $\geq \text{poly} (ε, 1/d)$. We show that for any polynomial $f: \{ \pm 1\}^n \rightarrow [0,1]$ of degree $d$ $(d \geq 2)$ and variance $\text{Var}[f] \geq 1/d$, if $ρ$ denotes a random restriction with survival probability $\dfrac{\log(d)}{C_1 d}$, $$ \text{Pr} \left[f_ρ \text{ has a coordinate with influence} \geq \dfrac{\text{Var}[f]^2 }{d^{C_2}} \right] \geq \dfrac{\text{Var}[f] \log(d)}{50C_1 d}$$ where $C_1, C_2>0$ are universal constants. Thus, Aaronson-Ambainis conjecture is true for a non-negligible fraction of random restrictions of the given polynomial assuming its variance is not too low.

arXiv:2402.13952•Leibniz international proceedings in informatics•Feb 21, 2024•4 citations

Distributed synthesis of arbitrary graph states in quantum networks via rank-two GF(2) reduction

Xiaoyi Zheng, Lin Chen, Chan-Tong Lam

Existing schemes for synthesizing graph states in quantum networks are essentially edge-by-edge constructions, so quantities such as the time-slot depth and the resource overhead grow significantly with the edge density of the target graph. This paper proposes a new method. Exploiting the mathematical equivalence between joint Pauli-X measurements and graph pivot operations, we formulate graph state synthesis as a rank-2 reduction process of a difference matrix over GF(2), and give an upper bound floor(N/2) on the number of steps for synthesizing an arbitrary N-node graph state, independent of the edge density of the target graph state. At the physical level, the joint Pauli-X measurement of each step is mapped to a dual-star concurrent distribution. We model the protocol on Waxman physical topologies with fiber attenuation and give a heuristic algorithm, and evaluate it against a strengthened Steiner baseline through Monte Carlo experiments. The experimental results show that our protocol is superior in time-slot depth almost everywhere. The entanglement resource overhead, the total number of CZ gates, and the number of Pauli measurements drop below the baseline near edge density p approximately 0.3, and are superior across the board thereafter. The denser the target graph state, the more significant the advantage.

quant-pharXiv:2608.21166•Aug 24, 2026•0 citations
The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if true, would imply that the acceptance probability of every ddd-query quantum algorithm can be well-approximated almost everywhere (i.e., on almost all inputs) by a poly(d)\mathrm{poly}(d)poly(d)-query classical algorithm. We prove a special case of the conjecture: in every completely bounded degree-ddd block-multilinear form with constant variance, there always exists a variable with influence at least 1/poly(d)1/\mathrm{poly}(d)1/poly(d). In a certain sense, such polynomials characterize the acceptance probability of quantum query algorithms, as shown by Arunachalam, Briët and Palazuelos (SICOMP '19). As a corollary we obtain efficient classical almost-everywhere simulation for a particular class of quantum algorithms that includes for instance kkk-fold Forrelation. Our main technical result relies on connections to free probability theory.
In an attempt to show that the acceptance probability of a quantum query algorithm making qqq queries can be well-approximated almost everywhere by a classical decision tree of depth ≤poly(q)\leq \text{poly}(q)≤poly(q), Aaronson and Ambainis proposed the following conjecture: let f:{±1}n→[0,1]f: \{ \pm 1\}^n \rightarrow [0,1]f:{±1}n→[0,1] be a degree ddd polynomial with variance ≥ε\geq ε≥ε. Then, there exists a coordinate of fff with influence ≥poly(ε,1/d)\geq \text{poly} (ε, 1/d)≥poly(ε,1/d). We show that for any polynomial f:{±1}n→[0,1]f: \{ \pm 1\}^n \rightarrow [0,1]f:{±1}n→[0,1] of degree ddd (d≥2)(d \geq 2)(d≥2) and variance Var[f]≥1/d\text{Var}[f] \geq 1/dVar[f]≥1/d, if ρρρ denotes a random restriction with survival probability log⁡(d)C1d\dfrac{\log(d)}{C_1 d}C1​dlog(d)​, Pr[fρ has a coordinate with influence≥Var[f]2dC2]≥Var[f]log⁡(d)50C1d \text{Pr} \left[f_ρ \text{ has a coordinate with influence} \geq \dfrac{\text{Var}[f]^2 }{d^{C_2}} \right] \geq \dfrac{\text{Var}[f] \log(d)}{50C_1 d}Pr[fρ​ has a coordinate with influence≥dC2​Var[f]2​]≥50C1​dVar[f]log(d)​ where C1,C2>0C_1, C_2>0C1​,C2​>0 are universal constants. Thus, Aaronson-Ambainis conjecture is true for a non-negligible fraction of random restrictions of the given polynomial assuming its variance is not too low.
Existing schemes for synthesizing graph states in quantum networks are essentially edge-by-edge constructions, so quantities such as the time-slot depth and the resource overhead grow significantly with the edge density of the target graph. This paper proposes a new method. Exploiting the mathematical equivalence between joint Pauli-X measurements and graph pivot operations, we formulate graph state synthesis as a rank-2 reduction process of a difference matrix over GF(2), and give an upper bound floor(N/2) on the number of steps for synthesizing an arbitrary N-node graph state, independent of the edge density of the target graph state. At the physical level, the joint Pauli-X measurement of each step is mapped to a dual-star concurrent distribution. We model the protocol on Waxman physical topologies with fiber attenuation and give a heuristic algorithm, and evaluate it against a strengthened Steiner baseline through Monte Carlo experiments. The experimental results show that our protocol is superior in time-slot depth almost everywhere. The entanglement resource overhead, the total number of CZ gates, and the number of Pauli measurements drop below the baseline near edge density p approximately 0.3, and are superior across the board thereafter. The denser the target graph state, the more significant the advantage.