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

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

Polynomial time quantum computation with advice

Harumichi Nishimura, Tomoyuki Yamakami

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

Recent Developments in Quantum Algorithms and Complexity

Andris Ambainis

Lecture notes in computer science•Jan 1, 2014•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

On quantum algorithms

Richard Cleve, ARTUR K. EKERT, Leah Henderson +2 more

Complexity•Sep 1, 1998•28 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.
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.