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

Lecture notes in computer science

Unbounded-Error Quantum Query Complexity

Ashley Montanaro, Harumichi Nishimura, Rudy Raymond

Published Jan 1, 2008• 8 citations
Publisher
DOI
10.1007/978-3-540-92182-0_80

Related papers

Unbounded-error quantum query complexity

Ashley Montanaro, Harumichi Nishimura, Rudy Raymond

arXiv:0712.1446•Theoretical Computer Science•May 3, 2011•14 citations

Nonadaptive quantum query complexity

Ashley Montanaro

arXiv:1001.0018•Information Processing Letters•Sep 22, 2010•16 citations

Zero-error expectation equals amortized query complexity

Daiki Suruga

This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expected randomized query complexity. For any total relation $f$ and any error tolerance $\varepsilon \in [0,1]$, we prove \[ \lim_{n \to \infty} \frac{\overline{R}_\varepsilon(f^n)}{n} = (1 - \varepsilon) \overline{R}_0(f). \] Thus the amortization converts bounded-error into zero error with the exact multiplicative factor $1-\varepsilon$. We also prove corresponding liminf/limsup bounds for worst-case randomized and distributional query complexity. These results improve prior direct-sum bounds that were known only up to constant factors or in restricted error regimes, and they resolve an open question posed by Blais and Brody (2019). Additionally for one-sided computation of the function $\operatorname{OR}_n \circ f$, we obtain analogous exact amortized identities for both expected and worst-case cost. As applications, we obtain separations between amortized and single-instance costs, including unbounded separations for distributional complexity and randomized relations, and a quadratic barrier for randomized total functions.

arXiv:2608.04152•Aug 4, 2026•0 citations

Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM

Fuyuki Kitagawa, Ryo Nishimaki, Agi Villanyi +1 more

We make progress towards the impossibility of quantum-computation, classical-communication (QCCC) key agreement by giving the first unconditional polynomial-query attacks that tolerate imperfect completeness in the following settings. First, we give a quantum attack on protocols with arbitrarily many rounds in which both parties' oracle queries and communication are classical before the final round, while local computation may be quantum throughout, and the final round may involve quantum oracle queries and one quantum message. Second, we give a classical attack on constant-round QCCC protocols in which Alice has classical oracle access and Bob may make quantum queries throughout. In both settings, the attacker is computationally unbounded and makes $poly(λ)$ queries to recover the key with nonnegligible probability whenever each party's total honest query bound is at most $poly(λ)$ and the valid agreement probability is inverse-polynomial. As consequences, we rule out query-bounded IND-CPA security for quantum public-key encryption with classical public and secret keys and classical messages of polynomially bounded length in the QROM in either of two settings: (i) key generation has classical oracle access, while encryption, decryption, and the ciphertext may be quantum; or (ii) encryption has classical oracle access and ciphertexts are classical, while key generation and decryption may have quantum oracle access. Both results assume negligible correctness error and polynomial honest query complexity. Combining the constant-round attack with the constructions of Bartusek and Khurana (CRYPTO 2025), we also rule out constant-round oblivious state preparation with polynomial honest query complexity and negligible correctness error in the QROM against computationally unbounded quantum receivers making polynomially many oracle queries.

quant-pharXiv:2608.17610•Aug 19, 2026•1 citation

Quantum query complexity, with advice

Can H. Bostanci

•Sep 16, 2026•0 citations

Post-selected Classical Query Complexity

Chris Cade

We study classical query algorithms with post-selection, and find that they are closely connected to rational functions with nonnegative coefficients. We show that the post-selected classical query complexity of a Boolean function is equal to the minimal degree of a rational function with nonnegative coefficients that approximates it (up to a factor of two). For post-selected quantum query algorithms, a similar relationship was shown by Mahadev and de Wolf, where the rational approximations are allowed to have negative coefficients. Using our characterisation, we find an exponentially large separation between post-selected classical query complexity and post-selected quantum query complexity, by proving a lower bound on the degree of rational approximations (with nonnegative coefficients) to the Majority function. This lower bound can be generalised to arbitrary symmetric functions, and allows us to find an unbounded separation between non-deterministic quantum and post-selected classical query complexity. All lower bounds carry over into the communication complexity setting. We show that the zero-error variants of post-selected query algorithms are equivalent to non-deterministic classical query algorithms, which in turn are characterised by nonnegative polynomials, and for some problems require exponentially more queries to the input than their bounded-error counterparts. Finally, we describe a post-selected query algorithm for approximating the Majority function, and an efficient query algorithm for approximate counting.

arXiv:1804.10010•Apr 26, 2018•1 citation
This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expected randomized query complexity. For any total relation fff and any error tolerance ε∈[0,1]\varepsilon \in [0,1]ε∈[0,1], we prove lim⁡n→∞R‾ε(fn)n=(1−ε)R‾0(f). \lim_{n \to \infty} \frac{\overline{R}_\varepsilon(f^n)}{n} = (1 - \varepsilon) \overline{R}_0(f). limn→∞​nRε​(fn)​=(1−ε)R0​(f). Thus the amortization converts bounded-error into zero error with the exact multiplicative factor 1−ε1-\varepsilon1−ε. We also prove corresponding liminf/limsup bounds for worst-case randomized and distributional query complexity. These results improve prior direct-sum bounds that were known only up to constant factors or in restricted error regimes, and they resolve an open question posed by Blais and Brody (2019). Additionally for one-sided computation of the function OR⁡n∘f\operatorname{OR}_n \circ fORn​∘f, we obtain analogous exact amortized identities for both expected and worst-case cost. As applications, we obtain separations between amortized and single-instance costs, including unbounded separations for distributional complexity and randomized relations, and a quadratic barrier for randomized total functions.
We make progress towards the impossibility of quantum-computation, classical-communication (QCCC) key agreement by giving the first unconditional polynomial-query attacks that tolerate imperfect completeness in the following settings. First, we give a quantum attack on protocols with arbitrarily many rounds in which both parties' oracle queries and communication are classical before the final round, while local computation may be quantum throughout, and the final round may involve quantum oracle queries and one quantum message. Second, we give a classical attack on constant-round QCCC protocols in which Alice has classical oracle access and Bob may make quantum queries throughout. In both settings, the attacker is computationally unbounded and makes poly(λ)poly(λ)poly(λ) queries to recover the key with nonnegligible probability whenever each party's total honest query bound is at most poly(λ)poly(λ)poly(λ) and the valid agreement probability is inverse-polynomial. As consequences, we rule out query-bounded IND-CPA security for quantum public-key encryption with classical public and secret keys and classical messages of polynomially bounded length in the QROM in either of two settings: (i) key generation has classical oracle access, while encryption, decryption, and the ciphertext may be quantum; or (ii) encryption has classical oracle access and ciphertexts are classical, while key generation and decryption may have quantum oracle access. Both results assume negligible correctness error and polynomial honest query complexity. Combining the constant-round attack with the constructions of Bartusek and Khurana (CRYPTO 2025), we also rule out constant-round oblivious state preparation with polynomial honest query complexity and negligible correctness error in the QROM against computationally unbounded quantum receivers making polynomially many oracle queries.
We study classical query algorithms with post-selection, and find that they are closely connected to rational functions with nonnegative coefficients. We show that the post-selected classical query complexity of a Boolean function is equal to the minimal degree of a rational function with nonnegative coefficients that approximates it (up to a factor of two). For post-selected quantum query algorithms, a similar relationship was shown by Mahadev and de Wolf, where the rational approximations are allowed to have negative coefficients. Using our characterisation, we find an exponentially large separation between post-selected classical query complexity and post-selected quantum query complexity, by proving a lower bound on the degree of rational approximations (with nonnegative coefficients) to the Majority function. This lower bound can be generalised to arbitrary symmetric functions, and allows us to find an unbounded separation between non-deterministic quantum and post-selected classical query complexity. All lower bounds carry over into the communication complexity setting. We show that the zero-error variants of post-selected query algorithms are equivalent to non-deterministic classical query algorithms, which in turn are characterised by nonnegative polynomials, and for some problems require exponentially more queries to the input than their bounded-error counterparts. Finally, we describe a post-selected query algorithm for approximating the Majority function, and an efficient query algorithm for approximate counting.