arXiv:2609.09804

Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method

Albert Lin, Han-Hsuan Lin

quant-phcs.CCSubmitted Sep 9, 2026• Announced Sep 10, 2026• 0 citations• Revised Oct 2, 2026 (v2)

Abstract

We study the two-weight decision version of quantum approximate counting: given oracle access to $x\in\{0,1\}^N$, distinguish $|x|=M$ from $|x|=M+Δ$ with success probability $1/2+ζ$. Using the multiplicative adversary method, we prove $Ω\left(\max\left\{ζ\sqrt{(N-M)(M+Δ)}/Δ,\sqrt{ζN/Δ}\right\}\right)$. The same parameter dependence follows from the polynomial-method characterization of the two-layer symmetric function by Podder, Yao, and Ye. Our contribution is a multiplicative-adversary derivation that tracks the progress produced by individual oracle queries. For the first term, after complementing the input if necessary, we assume $M+Δ\le N-M$. We use the Hamming-layer subspaces from the eigenspace method of Ambainis, Spalek, and de Wolf and compose their adjacent-layer unitary maps to relate the two nonadjacent promise layers. After fixing the queried coordinate, the analysis block-diagonalizes into four-dimensional subspaces. An exact calculation of the one-query progress ratio gives the first lower bound. The same estimate also implies $\left\|(I-\widehatΠ_{\mathrm{bad}})\lvertΨ^T\rangle\right\|^2=O\left(T^2Δ^2/((N-M)(M+Δ))\right)$ for the coherent input superposition used in the adversary argument. For the second term, we prove directly using a three-eigenvalue multiplicative adversary that unique OR on $n$ bits with success probability $1/2+ζ$ requires $Ω(\sqrt{ζn})$ queries, and then reduce unique OR to the two-weight counting problem.

Comments: 18 pages

Related papers

Quantum Approximate Counting with Bernoulli Oracles

Chengshen Gao, Yongzhen Xu, Lvzhou Li

quant-pharXiv:2609.07604Sep 8, 20260 citations

One Weird Trick Tightens the Quantum Adversary Bound, Especially for Success Probability Close to $1/2$

Duyal Yolcu

arXiv:2303.10244Mar 17, 20230 citations

Variations on Quantum Adversary

Aleksandrs Belovs

arXiv:1504.06943Apr 27, 201511 citations

Lower Bounds for Preprocessing Attacks on Quantum Cryptography

Fangqi Dong, Alex Lombardi

quant-pharXiv:2610.02101Oct 2, 20260 citations

BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting

Sevag Gharibian, Jonas Kamminga

arXiv:2401.03943Leibniz international proceedings in informaticsJan 1, 20240 citations

Tight bounds for hybrid quantum-classical query algorithms

Andris Ambainis, András Gilyén, Martins Kokainis

quant-pharXiv:2610.06803Oct 6, 20260 citations

arXiv:2609.09804

Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method

Albert Lin, Han-Hsuan Lin

quant-phcs.CCSubmitted Sep 9, 2026• Announced Sep 10, 2026• 0 citations• Revised Oct 2, 2026 (v2)

arXiv HTML PDF

Abstract

We study the two-weight decision version of quantum approximate counting: given oracle access to

x\in\{0,1\}^N

, distinguish

|x|=M

from

|x|=M+Δ

with success probability

1/2+ζ

. Using the multiplicative adversary method, we prove

Ω\left(\max\left\{ζ\sqrt{(N-M)(M+Δ)}/Δ,\sqrt{ζN/Δ}\right\}\right)

. The same parameter dependence follows from the polynomial-method characterization of the two-layer symmetric function by Podder, Yao, and Ye. Our contribution is a multiplicative-adversary derivation that tracks the progress produced by individual oracle queries. For the first term, after complementing the input if necessary, we assume

M+Δ\le N-M

. We use the Hamming-layer subspaces from the eigenspace method of Ambainis, Spalek, and de Wolf and compose their adjacent-layer unitary maps to relate the two nonadjacent promise layers. After fixing the queried coordinate, the analysis block-diagonalizes into four-dimensional subspaces. An exact calculation of the one-query progress ratio gives the first lower bound. The same estimate also implies

\left\|(I-\widehatΠ_{\mathrm{bad}})\lvertΨ^T\rangle\right\|^2=O\left(T^2Δ^2/((N-M)(M+Δ))\right)

for the coherent input superposition used in the adversary argument. For the second term, we prove directly using a three-eigenvalue multiplicative adversary that unique OR on

n

bits with success probability

1/2+ζ

requires

Ω(\sqrt{ζn})

queries, and then reduce unique OR to the two-weight counting problem.

Comments: 18 pages

Related papers

Quantum Approximate Counting with Bernoulli Oracles

Chengshen Gao, Yongzhen Xu, Lvzhou Li

Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given $m$ Bernoulli distributions with unknown biases $p_1,\dots,p_m$ and a gap parameter $Δ$ , the goal is to estimate the fraction $ρ$ of \emph{positive} distributions ( $p_i\ge1/2+Δ$ ) to within additive error $ε$ . We prove an upper bound of $\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)$ queries, achieving a quadratic speedup over the classical sample complexity. % of $Θ(ρ/Δ^2ε^2)$ . Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of $Ω(\sqrtρ/(Δε))$ via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap $Δ=Θ(1)$ , which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to $\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)$ and $Ω(\frac{\sqrtρ}ε)$ , thereby characterizing the query complexity of quantum counting with bounded-error oracles.Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given $m$ Bernoulli distributions with unknown biases $p_1,\dots,p_m$ and a gap parameter $Δ$, the goal is to estimate the fraction $ρ$ of \emph{positive} distributions ($p_i\ge1/2+Δ$) to within additive error $ε$. We prove an upper bound of $\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)$ queries, achieving a quadratic speedup over the classical sample complexity. % of $Θ(ρ/Δ^2ε^2)$. Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of $Ω(\sqrtρ/(Δε))$ via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap $Δ=Θ(1)$, which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to $\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)$ and $Ω(\frac{\sqrtρ}ε)$, thereby characterizing the query complexity of quantum counting with bounded-error oracles.

quant-pharXiv:2609.07604Sep 8, 20260 citations

One Weird Trick Tightens the Quantum Adversary Bound, Especially for Success Probability Close to $1/2$ One Weird Trick Tightens the Quantum Adversary Bound, Especially for Success Probability Close to $1/2$

Duyal Yolcu

The textbook adversary bound for function evaluation states that to evaluate a function $f\colon D\to C$ with success probability $\frac{1}{2}+δ$ in the quantum query model, one needs at least $\left( 2δ-\sqrt{1-4δ^2} \right) Adv(f)$ queries, where $Adv(f)$ is the optimal value of a certain optimization problem. For $δ\ll 1$ , this only allows for a bound of $Θ\left(δ^2 Adv(f)\right)$ even after a repetition-and-majority-voting argument. In contrast, the polynomial method can sometimes prove a bound that doesn't converge to $0$ as $δ\to 0$ . We improve the $δ$ -dependent prefactor and achieve a bound of $2δAdv(f)$ . The proof idea is to "turn the output condition into an input condition": From an algorithm that transforms perfectly input-independent initial to imperfectly distinguishable final states, we construct one that transforms imperfectly input-independent initial to perfectly distinguishable final states in the same number of queries by projecting onto the "correct" final subspaces and uncomputing. The resulting $δ$ -dependent condition on initial Gram matrices, compared to the original algorithm's condition on final Gram matrices, allows deriving the tightened prefactor.The textbook adversary bound for function evaluation states that to evaluate a function $f\colon D\to C$ with success probability $\frac{1}{2}+δ$ in the quantum query model, one needs at least $\left( 2δ-\sqrt{1-4δ^2} \right) Adv(f)$ queries, where $Adv(f)$ is the optimal value of a certain optimization problem. For $δ\ll 1$, this only allows for a bound of $Θ\left(δ^2 Adv(f)\right)$ even after a repetition-and-majority-voting argument. In contrast, the polynomial method can sometimes prove a bound that doesn't converge to $0$ as $δ\to 0$. We improve the $δ$-dependent prefactor and achieve a bound of $2δAdv(f)$. The proof idea is to "turn the output condition into an input condition": From an algorithm that transforms perfectly input-independent initial to imperfectly distinguishable final states, we construct one that transforms imperfectly input-independent initial to perfectly distinguishable final states in the same number of queries by projecting onto the "correct" final subspaces and uncomputing. The resulting $δ$-dependent condition on initial Gram matrices, compared to the original algorithm's condition on final Gram matrices, allows deriving the tightened prefactor.

arXiv:2303.10244Mar 17, 20230 citations

Variations on Quantum Adversary

Aleksandrs Belovs

The (negative-weighted) quantum adversary bound is a tight characterisation of the quantum query complexity for any partial function. We analyse the extent to which this bound can be generalised. Ambainis et al. [arXiv:1012.2112] and Lee et al. [arXiv:1011.3020] generalised this bound to the state generation and state conversion problems, respectively. Using the ideas by Lee et al., we get even further generalisations of the bound. We obtain a version of the bound for general input oracles, which are just arbitrary unitaries. We also generalise the bound to the problem of implementing arbitrary unitary transformations. Similarly to the bound by Lee et al., our bound is a lower bound for exact transformation and an upper bound for approximate transformation. This version of the bound possesses the tight composition property. Using this construction, we also obtain lower bounds on the quantum query complexity of functions and relations with general input oracles.The (negative-weighted) quantum adversary bound is a tight characterisation of the quantum query complexity for any partial function. We analyse the extent to which this bound can be generalised. Ambainis et al. [arXiv:1012.2112] and Lee et al. [arXiv:1011.3020] generalised this bound to the state generation and state conversion problems, respectively. Using the ideas by Lee et al., we get even further generalisations of the bound. We obtain a version of the bound for general input oracles, which are just arbitrary unitaries. We also generalise the bound to the problem of implementing arbitrary unitary transformations. Similarly to the bound by Lee et al., our bound is a lower bound for exact transformation and an upper bound for approximate transformation. This version of the bound possesses the tight composition property. Using this construction, we also obtain lower bounds on the quantum query complexity of functions and relations with general input oracles.

arXiv:1504.06943Apr 27, 201511 citations

Lower Bounds for Preprocessing Attacks on Quantum Cryptography

Fangqi Dong, Alex Lombardi

We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a $T$ -query adversary with $S$ qubits of non-uniform advice can recover a random key $k$ from the $n$ -qubit binary phase state $|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle$ with probability at most $O(\frac{T^2 + \sqrt{ST}}{N})$ for $N=2^n$ . In contrast, the best known bound for post-quantum one-way functions is $O(\frac{T^2 + ST}{N})$ , with a trivial attack at $S = N$ . This demonstrates a new advantage of quantum cryptography over classical cryptography: $n$ qubits of communication suffice for security against preprocessing attacks with space up to $N^2$ rather than $N$ . Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of $O(\frac{T^2}N + \sqrt{\frac{ST}N})$ . (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight $O(\frac{\sqrt{S}}N)$ bound for the pseudorandomness of random binary phase states against space $S$ distinguishers.We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a $T$-query adversary with $S$ qubits of non-uniform advice can recover a random key $k$ from the $n$-qubit binary phase state $|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle$ with probability at most $O(\frac{T^2 + \sqrt{ST}}{N})$ for $N=2^n$. In contrast, the best known bound for post-quantum one-way functions is $O(\frac{T^2 + ST}{N})$, with a trivial attack at $S = N$. This demonstrates a new advantage of quantum cryptography over classical cryptography: $n$ qubits of communication suffice for security against preprocessing attacks with space up to $N^2$ rather than $N$. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of $O(\frac{T^2}N + \sqrt{\frac{ST}N})$. (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight $O(\frac{\sqrt{S}}N)$ bound for the pseudorandomness of random binary phase states against space $S$ distinguishers.

quant-pharXiv:2610.02101Oct 2, 20260 citations

BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting

Sevag Gharibian, Jonas Kamminga

What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires $Θ(n)$ queries to an NP oracle to compute a witness to a given SAT formula, quantumly $Θ(\log n)$ queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires $Ω(\log n)$ queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires $Ω(\log n)$ queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making $o(log n)$ NP queries, then $\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$ -complete problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$ contains an $\text{FP}^{\text{NP}}$ -complete problem if the algorithm is quantum.What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires $Θ(n)$ queries to an NP oracle to compute a witness to a given SAT formula, quantumly $Θ(\log n)$ queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires $Ω(\log n)$ queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires $Ω(\log n)$ queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making $o(log n)$ NP queries, then $\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$ contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is quantum.

arXiv:2401.03943Leibniz international proceedings in informaticsJan 1, 20240 citations

Tight bounds for hybrid quantum-classical query algorithms

Andris Ambainis, András Gilyén, Martins Kokainis

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$ , the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.

quant-pharXiv:2610.06803Oct 6, 20260 citations

We study the two-weight decision version of quantum approximate counting: given oracle access to

x\in\{0,1\}^N

, distinguish

|x|=M

from

|x|=M+Δ

with success probability

1/2+ζ

. Using the multiplicative adversary method, we prove

Ω\left(\max\left\{ζ\sqrt{(N-M)(M+Δ)}/Δ,\sqrt{ζN/Δ}\right\}\right)

M+Δ\le N-M

\left\|(I-\widehatΠ_{\mathrm{bad}})\lvertΨ^T\rangle\right\|^2=O\left(T^2Δ^2/((N-M)(M+Δ))\right)

for the coherent input superposition used in the adversary argument. For the second term, we prove directly using a three-eigenvalue multiplicative adversary that unique OR on

n

bits with success probability

1/2+ζ

requires

Ω(\sqrt{ζn})

queries, and then reduce unique OR to the two-weight counting problem.

m

Bernoulli distributions with unknown biases

p_1,\dots,p_m

and a gap parameter

Δ

, the goal is to estimate the fraction

ρ

of \emph{positive} distributions (

p_i\ge1/2+Δ

) to within additive error

ε

. We prove an upper bound of

\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)

queries, achieving a quadratic speedup over the classical sample complexity. % of

Θ(ρ/Δ^2ε^2)

. Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of

Ω(\sqrtρ/(Δε))

via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap

Δ=Θ(1)

, which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to

\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)

and

Ω(\frac{\sqrtρ}ε)

, thereby characterizing the query complexity of quantum counting with bounded-error oracles.

One Weird Trick Tightens the Quantum Adversary Bound, Especially for Success Probability Close to

1/2

The textbook adversary bound for function evaluation states that to evaluate a function

f\colon D\to C

with success probability

\frac{1}{2}+δ

in the quantum query model, one needs at least

\left( 2δ-\sqrt{1-4δ^2} \right) Adv(f)

queries, where

Adv(f)

is the optimal value of a certain optimization problem. For

δ\ll 1

, this only allows for a bound of

Θ\left(δ^2 Adv(f)\right)

even after a repetition-and-majority-voting argument. In contrast, the polynomial method can sometimes prove a bound that doesn't converge to

0

δ\to 0

. We improve the

δ

-dependent prefactor and achieve a bound of

2δAdv(f)

. The proof idea is to "turn the output condition into an input condition": From an algorithm that transforms perfectly input-independent initial to imperfectly distinguishable final states, we construct one that transforms imperfectly input-independent initial to perfectly distinguishable final states in the same number of queries by projecting onto the "correct" final subspaces and uncomputing. The resulting

δ

-dependent condition on initial Gram matrices, compared to the original algorithm's condition on final Gram matrices, allows deriving the tightened prefactor.

We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a

T

-query adversary with

S

qubits of non-uniform advice can recover a random key

k

from the

n

-qubit binary phase state

|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle

with probability at most

O(\frac{T^2 + \sqrt{ST}}{N})

for

N=2^n

. In contrast, the best known bound for post-quantum one-way functions is

O(\frac{T^2 + ST}{N})

, with a trivial attack at

S = N

. This demonstrates a new advantage of quantum cryptography over classical cryptography:

n

qubits of communication suffice for security against preprocessing attacks with space up to

N^2

rather than

N

. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of

O(\frac{T^2}N + \sqrt{\frac{ST}N})

. (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight

O(\frac{\sqrt{S}}N)

bound for the pseudorandomness of random binary phase states against space

S

distinguishers.

Θ(n)

queries to an NP oracle to compute a witness to a given SAT formula, quantumly

Θ(\log n)

queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires

Ω(\log n)

queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires

Ω(\log n)

queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making

o(log n)

NP queries, then

\text{BPP}^{\text{NP}[o(n)]}

contains a

\text{P}^{\text{NP}}

-complete problem if the algorithm is classical and

\text{FBQP}^{\text{NP}[o(n)]}

contains an

\text{FP}^{\text{NP}}

-complete problem if the algorithm is quantum.

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most

q

oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision

ε

requires

Θ(\frac{1}{q ε^2})

queries; (ii) (Unbiased) Amplitude estimation up to a precision

ε

requires

Θ(\frac{p(1-p)}{q ε^2})

queries; (iii) Search among

N

items requires

Θ(\frac{N}{q})

queries; (iv) Two level AND-OR tree (AND of

m

ORs, with

n

inputs to each OR) requires

Θ(\frac{nm}{q})

queries. All of these bounds are optimal up to a constant factor, for all

q

from 1, corresponding to the classical complexity, to

Q(f)

, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.