NISQ Security and Complexity via Simple Classical Reasoning

Alexandru Cojocaru; Fang Song; Juan Garay; Qipeng Liu

REVIEW 4 major objections 4 minor 6 references

NISQ Security and Complexity via Simple Classical Reasoning

T0 review · 4 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims a single hybrid lifting theorem: any hybrid (q quantum, c classical) adversary against a k-query classical challenger implies a k-query adversary whose success is at least Pr[A] / O(q^2/k^2 + c/k)^k.

desk verdict A genuinely useful lifting framework for hybrid NISQ security, but the central orthogonality claim (Eq. 6) has a real gap that needs fixing before the result is proven as stated. read the letter →

arxiv 2509.09900 v1 pith:ETANUKCD submitted 2025-09-11 quant-ph cs.CCcs.CR

Alexandru Cojocaru , Juan Garay , Qipeng Liu , Fang Song This is my paper · ORCID

classification quant-phcs.CCcs.CR MSC 68Q1281P9494A60

keywords hybridalgorithmsliftingtheoremquantumrandomoraclemodelmeasure-and-reprogramNISQdirectproductquerycomplexitycryptographichardness

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper's central claim is a lifting theorem for security games in which an attacker may mix quantum and classical random-oracle queries. It proves that any hybrid attacker with q quantum and c classical queries that wins a game against a k-query classical challenger with probability epsilon can be converted into a k-query attacker winning with probability at least epsilon / O(q^2/k^2 + c/k)^k. The technical engine is a 'hybrid coherent measure-and-reprogram' simulator that reprograms up to k oracle answers while controlling when measurements and reprogrammings occur, losing only a combinatorial factor A_{k,q,c}. From this one theorem, the paper derives direct product theorems and hybrid hardness for multi-image inversion, multi-collision, multi-search, salted games, and 3SUM. A sympathetic reader would care because it turns NISQ security analysis into one classical combinatorial calculation.

What carries the argument

The central object is the hybrid coherent measure-and-reprogram experiment: a simulator runs the hybrid algorithm while choosing k query positions, deciding for each whether to measure-and-reprogram before or after the query, and using a control/history register to track (x, G(x)) pairs. The key identity is the combinatorial sum A_{k,q,c} = sum_t (q choose t)^2 (k choose t)(c choose k-t), bounded by O(q^2/k^2 + c/k)^k; it quantifies the probability that the simulator picks exactly t quantum queries to reprogram. The simulator's success probability is inversely proportional to A_{k,q,c}, and this single quantity becomes the universal loss for all applications.

What would settle it

Take a small explicit hybrid algorithm (say k=2, q=1, c=2) for a 2-image search, implement the two decomposed states corresponding to two different classical reprogramming schedules, and compute their inner product: a nonzero value would violate the orthogonality asserted in the proof's inequality (6) and invalidate the bound.

Watch

Extended reading notes

Core claim

The core discovery is a hybrid coherent measure-and-reprogram theorem. For any static hybrid algorithm making q quantum and c classical queries to an oracle, and any k-point reprogramming of that oracle, there is a simulator that makes only k queries to a second random oracle and reproduces the algorithm's success with probability at least 1/(2^{2k} k A_{k,q,c}) of the original, where A_{k,q,c} = sum_t (q choose t)^2 (k choose t)(c choose k-t) simplifies to O(q^2/k^2 + c/k)^k. From this, the lifting theorem follows: any hybrid adversary against a k-query classical challenger can be replaced by a k-query adversary with the stated loss. The authors then show the bound is optimal for multi-imag

Load-bearing premise

The proof relies on the states generated by different choices of which classical queries to reprogram being exactly orthogonal as recorded in the history register; if that orthogonality fails for any algorithm, the Cauchy-Schwarz step that produces the main bound collapses.

Editorial extensions

If this is right

If a search game is hard for any k-query hybrid adversary, then it is hard for arbitrary hybrid adversaries up to the loss factor O(q^2/k^2 + c/k)^k.
The hybrid direct product theorem implies that solving g independent instances with g q quantum and g c classical queries has success at most [O(q^2/k^2 + c/k)^k p(R)]^g, enabling multi-instance hardness.
Non-uniform hybrid adversaries with S bits of classical advice are bounded by O((S^2 q^2/k^2 + S c/k))^{k/S} p(R^{⊗S})^{1/S}.
Salting defeats preprocessing: salted games become 4S/K + O(q^2/k^2 + c/k)^k p(R) secure against hybrid adversaries with S bits of advice.
The framework yields upper bounds for multi-image inversion (tight), multi-collision, multi-search, and 3SUM in the hybrid query model.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same simulator template could be adapted to prove lifting for interactive protocols where the challenger itself makes quantum queries, extending the framework beyond classical-challenger games.
The bound suggests the natural hybrid resource is q^2 + c; protocols could be parameterized on this combined quantity, and practical NISQ experiments might test whether attack success follows this trade-off.
For noisy oracles the authors note non-tightness at constant p; a concrete open test is whether explicit function inversion matches O(T^2/N) or the classical O(T/N), indicating where the lifting bound loses.
One could apply the framework to new games by computing p(R) alone and reading off hybrid hardness without further analysis, for relations defined by linear statistics or other permutation-invariant image predicates.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The short version: this is a useful lifting framework for NISQ security, and if the central theorem is right it will save a lot of ad-hoc analysis. But the core proof has a real gap that the authors need to close before the result is proven as stated.

What's genuinely new: a hybrid coherent measure-and-reprogram theorem that handles algorithms issuing both quantum and classical queries, with a loss factor O(q^2/k^2 + c/k)^k. It gives the first hybrid direct product theorem in the average case and a clean way to get hardness for multi-image inversion, multi-collision, 3SUM, salting, and non-uniform adversaries. The applications are essentially direct consequences of computing a single combinatorial quantity p(R). That is a significant modularity improvement over prior work like [HLS24] and [CGS23], which were tailored to specific problems.

Where I have concerns. The stress-test is right: Eq. (6) is not an identity for arbitrary H,G. The history register only distinguishes two classic reprogramming schedules when the oracle value at the reprogrammed point differs from the original value. If G(x)=H(x), the branches have identical histories, so the claimed orthogonality fails. Since the theorem is stated for all H,G, the proof as written does not go through. The fix is probably to work with random H,G, show the bad event has small probability, and absorb that into the constant—but that needs to be done explicitly. As it stands, the claimed bound is not justified.

Other soft spots: Section 3.2 is a sketch leaning heavily on [CGLS25], which makes it hard to verify the state decomposition independently; the noisy-oracle result is explicitly non-tight away from the endpoints p=0,1 (they acknowledge this, but it limits the result's usefulness); and there is a minor counting inconsistency in Lemma 3.7 about whether the final k classical queries are included in the reprogramming locations, which affects the loss factor.

Who should read this: anyone working on QROM lifting theorems, hybrid quantum-classical security, or NISQ hardness. It's a good paper to bring to a reading group because the high-level idea is clean and there is a substantive technical gap to discuss.

Recommendation: this deserves a serious referee. I would not accept it in its current form—the Eq. (6) gap is load-bearing—but with that fixed and the proof expanded, it should be a strong paper.

Referee Report

4 major / 4 minor

Summary. The paper introduces a 'hybrid coherent measure-and-reprogram' framework for security games in the quantum random oracle model, targeting NISQ settings. The central claim (Theorem 3.1) is a lifting theorem: for any hybrid algorithm with q quantum and c classical queries, there is a simulator making only k queries that wins with probability at least 1/O((q^2/k^2 + c/k))^k times the original algorithm's success probability. The authors also state lifting theorems for noisy oracles and bounded-depth algorithms, and derive applications including direct-product theorems, salting against non-uniform adversaries, and hardness bounds for multi-image inversion, multi-collision finding, multi-search, and 3SUM. The framework is intended to reduce NISQ security to the computation of a single classical quantity p(R).

Significance. If the main theorem and its proof were correct, this would be a substantial contribution: it would provide the first general hybrid lifting theorem, a unified technique for deriving NISQ hardness across many search games, and a direct-product theorem for hybrid adversaries. The claimed reduction of security to a simple combinatorial quantity p(R) is attractive and would extend the recent coherent measure-and-reprogram approach of [CGLS25] to a practically motivated model. The paper also gives optimality claims for multi-image search, which would demonstrate tightness of the framework. However, the proof of the central theorem contains a load-bearing orthogonality assertion that is not justified and is in fact false under the paper's own definitions, and there is a clear counting inconsistency between the simulator definition and the probability computations. These issues prevent the current manuscript from establishing its main results.

major comments (4)

[Section 3.2, Eq. (6)] The orthogonality assertion in Eq. (6) is not correct. The history register records (x, H(x)) for non-reprogrammed classical queries and (x, G(x)) for reprogrammed ones. For x in the reprogrammed set \vec{x}_o, however, H^{\vec{x}_o,\vec{y}_o}(x) = G(x) by construction, so the recorded pairs coincide. Since the final projection fixes the output to \vec{x}_o, the relevant classical query inputs are in \vec{x}_o, making the two histories indistinguishable in general. Consequently Eq. (7) does not follow; cross terms may introduce an additional combinatorial factor proportional to the number of classical reprogramming choices, potentially invalidating the claimed O(q^2/k^2 + c/k)^k loss.
[Lemma 3.7 vs. Definition 3.3] There is a counting mismatch. Definition 3.3 samples the reprogramming positions v from [c+q+k], including the k final 'typing' queries, so the number of choices with exactly t quantum positions is (q choose t)(c+k choose k-t). Lemma 3.7 instead uses (q choose t)(c choose k-t). This discrepancy affects the normalization in the definition of a_t (Definition 3.8) and the final loss factor. It is not a cosmetic issue: the theorem statement's A_{k,q,c} may correspond to a different sampling procedure than the one actually analyzed.
[Proof of Lemma 3.6] The proof is a sketch and delegates the central state decomposition to the proof of Theorem 6 in [CGLS25], which is not reproduced. The hybrid adaptation—especially the treatment of the final k classical queries and the claim that one can 'measure-and-(immediately)-reprogram exactly k-l locations of the last k queries'—is asserted without derivation. Given that the entire theorem rests on this decomposition, the referee cannot verify that the stated constants (e.g., the factor k and the binomial coefficients) are correct.
[Remark 3.2] The paper states the main theorem only for static hybrid algorithms (where the order of classical and quantum queries is fixed) and says the general adaptive case follows from [DFH22] with a factor-2 loss. Since several applications are phrased for arbitrary hybrid algorithms, this extension is load-bearing, but no proof is given and the exact way [DFH22] applies to the present simulator is not specified.

minor comments (4)

[Abstract / Introduction] The informal Theorem 1.1 says 'k (quantum + classical) hybrid query adversary' but it is not immediately clear whether the simulator's k queries include both types; the formal Theorem 3.1 clarifies that Sim makes exactly k queries to G, but the informal phrasing could be tightened.
[Definition 3.3, step 2] The condition '1 < v_1 < ... < v_k <= c+q+k' appears to have a typo: the lower bound should likely be 1, not 1 < v_1, and the ordering should be non-decreasing or strictly increasing depending on whether duplicate positions are allowed.
[Section 3.5, Lemma 3.11] The proof of optimality shows an upper bound on A_{k,q,c} but the matching lower bound is only argued for constant k. The claim for general k would benefit from a more explicit comparison of constants.
[Equation (9)] The factor 1/2^k in Lemma 3.7 seems to be lost in the displayed equation after substitution of a_t; the final expression in the proof of Theorem 3.1 should be checked for consistency of the powers of 2.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the hybrid lifting theorem is derived from an explicit simulator construction and independent combinatorial bounds, not from its own inputs.

full rationale

The paper's derivation chain is not circular. The central result, Theorem 3.1, is obtained by constructing an explicit simulator (Definition 3.3) and then relating the success probability of the original algorithm A to the simulator B through two separate bounds: Lemma 3.6 upper-bounds A's success by a weighted sum of simulator success probabilities p_{x0,v,b}, and Lemma 3.7 lower-bounds B's success by the same sum with the sampling probabilities of (v,b). The loss factor A_{k,q,c} is a purely combinatorial quantity defined independently in Definition 3.8 and bounded in Lemma 3.12 using standard binomial/AM-GM estimates; the distribution a_t is chosen after the fact to cancel out, not fitted to the target. The applications then instantiate the lifting theorem by computing p(R), a classical probability over random images, which is not an input to the theorem. The main proof does import the decomposition skeleton from the authors' prior [CGLS25] ('The decomposition step follows closely the idea from the purely quantum setting (proof of Theorem 6 in [CGLS25])', Section 3.2) and the optimality proof uses [CGS23] for a single-target hybrid search lower bound, but these are base theorems for different settings (purely quantum, and single-image hybrid search) rather than restatements of the present hybrid lifting claim; no equation in the paper reduces to its own input by definition. The possible failure of the orthogonality assertion in Eq. (6) when reprogrammed and original values coincide, and the counting mismatch involving (c choose k-t), are correctness/rigor concerns about the proof, not instances of circular reasoning.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The central claim rests on standard QROM assumptions, a hand-chosen internal distribution a_t that cancels in the final bound, and two load-bearing technical premises: the history-register orthogonality (Eq. 6) and the seamless extension of the [CGLS25] decomposition to hybrid algorithms. No new physical entities or fitted constants are introduced; p(R) is a purely combinatorial quantity computed independently for each application.

free parameters (1)

a_t distribution over number of quantum queries reprogrammed = alpha_t = (q choose t)^2 (k choose t)(c choose k-t) / A_{k,q,c}
Chosen by hand in Definition 3.8 to minimize the internal loss of the hybrid measure-and-reprogram experiment. It is not fitted to any target result and cancels out of the final theorem statement.

assumptions (6)

standard math Cauchy-Schwarz and AM-GM inequalities used repeatedly (Eq. 2, 3, 4, Lemma 3.12)
Standard inequalities applied to decompose and recombine quantum states; no controversy.
domain assumption Without loss of generality, hybrid algorithms have pure states and no measurements until the end, with classical queries purified via a history register (Sec. 2.1)
Standard purification argument in QROM literature; makes the analysis of classical queries tractable.
domain assumption Static hybrid algorithms are equivalent to adaptive ones up to a constant factor in query count (Remark 3.2, citing [DFH22])
The main theorem is proved for static query patterns; the paper extends to adaptive algorithms by citing [DFH22], which is not reproved.
ad hoc to paper Orthogonality of states for different classical reprogramming schedules via the history register (Eq. 6)
The key structural claim that lets the paper avoid mixed states when combining classical and quantum reprogramming. Stated but not fully proved; if false, the causal compression of Lemma 3.6 fails.
domain assumption The state decomposition of the purely quantum coherent reprogramming proof in [CGLS25] extends to hybrid algorithms (Sec. 3.2)
The paper says 'this follows closely the idea from the purely quantum setting' and does not reproduce the full detail; correctness rests on that prior proof.
domain assumption Depth-bounded algorithms reduce to noisy oracles via Lemma 4.3 from [HLS24]
Bounded-depth lifting is obtained as a corollary of the noisy oracle theorem using this cited reduction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of NISQ Security and Complexity via Simple Classical Reasoning." pith.science (2026). https://pith.science/paper/ETANUKCD

@misc{pith2026250909900,
  author       = {Pith},
  title        = {Pith review of: NISQ Security and Complexity via Simple Classical Reasoning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ETANUKCD}},
  note         = {Machine review of arXiv:2509.09900}
}

read the original abstract

We give novel lifting theorems for security games in the quantum random oracle model (QROM) in Noisy Intermediate-Scale Quantum (NISQ) settings such as the hybrid query model, the noisy oracle and the bounded-depth models. We provide, for the first time, a hybrid lifting theorem for hybrid algorithms that can perform both quantum and classical queries, as well as a lifting theorem for quantum algorithms with access to noisy oracles or bounded quantum depth. At the core of our results lies a novel measure-and-reprogram framework, called hybrid coherent measure-and-reprogramming, tailored specifically for hybrid algorithms. Equipped with the lifting theorem, we are able to prove directly NISQ security and complexity results by calculating a single combinatorial quantity, relying solely on classical reasoning. As applications, we derive the first direct product theorems in the average case, in the hybrid setting-i.e., an enabling tool to determine the hybrid hardness of solving multi-instance security games. This allows us to derive in a straightforward manner the NISQ hardness of various security games, such as (i) the non-uniform hardness of salted games, (ii) the hardness of specific cryptographic tasks such as the multiple instance version of one-wayness and collision-resistance, and (iii) uniform or non-uniform hardness of many other games.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

6 extracted references · 1 linked inside Pith

[1]

The random oracle function is defined as:𝐺= (𝐻 1, ..., 𝐻𝐾)for𝐾random functions𝐻 𝑖 : [𝑀]→ [𝑁]
[2]

For any such𝐺, the challenge𝑐𝑕:= (𝑖, 𝑐𝑕 𝑖)is produced by first sampling uniformly at random 𝑖∈[𝐾]and then sampling𝑐𝑕 𝑖 according to𝜋 𝐻𝑖
[3]

Probabilistic Hash-and-Sign with Retry in the Quan- tum Random Oracle Model

2021, pp. 580–610 (cit. on p. 8). [KX24] Haruhisa Kosuge and Keita Xagawa. “Probabilistic Hash-and-Sign with Retry in the Quan- tum Random Oracle Model”. In:Public-Key Cryptography – PKC 2024. 2024, pp. 259– 288 (cit. on p. 8). [LR13] Troy Lee and Jérémie Roland. “A strong direct product theorem for quantum query complexity”. In:computational complexity22...

arXiv 2021
[6]

Lemma A.6(Hybrid Security of Salted Game against Classical Advice).Let𝒢be a multi-output𝑘- search game (as defined in Def

The winning relation is defined as𝑅 𝐺,𝑐𝑕 :=𝑅 𝐻𝑖,𝑐𝑕𝑖; We will denote by𝜖𝒢𝑠(𝑞, 𝑐)the maximum probability over all𝑞-quantum and𝑐-classical hybrid algorithms 𝒜of winning the salted game𝒢 𝑠. Lemma A.6(Hybrid Security of Salted Game against Classical Advice).Let𝒢be a multi-output𝑘- search game (as defined in Def. 5.1), specified by a relation𝑅. Let𝒢 𝑠 be the sa...
[2021]

The bitcoin backbone proto- col: Analysis and applications

2021, pp. 637–667 (cit. on p. 8). [GKL15] Juan A Garay, Aggelos Kiayias, and Nikos Leonardos. “The bitcoin backbone proto- col: Analysis and applications”. In:Journal of the ACM(2015) (cit. on pp. 8, 36). [HLS24] Yassine Hamoudi, Qipeng Liu, and Makrand Sinha. “The NISQ Complexity of Col- lision Finding”. In:Advances in Cryptology – EUROCRYPT 2024: 43rd A...

2021
[2022]

Tight Characterizations for Preprocess- ing against Cryptographic Salting

2022, pp. 677–706 (cit. on pp. 8, 9). [DLW24] Fangqi Dong, Qipeng Liu, and Kewen Wu. “Tight Characterizations for Preprocess- ing against Cryptographic Salting”. In:Annual International Cryptology Conference. Springer. 2024 (cit. on pp. 6, 7, 35). [GHHM21] Alex B. Grilo, Kathrin Hövelmanns, Andreas Hülsing, and Christian Majenz. “Tight Adaptive Reprogramm...

2022

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

The random oracle function is defined as:𝐺= (𝐻 1, ..., 𝐻𝐾)for𝐾random functions𝐻 𝑖 : [𝑀]→ [𝑁]

[2] [2]

For any such𝐺, the challenge𝑐𝑕:= (𝑖, 𝑐𝑕 𝑖)is produced by first sampling uniformly at random 𝑖∈[𝐾]and then sampling𝑐𝑕 𝑖 according to𝜋 𝐻𝑖

[3] [3]

Probabilistic Hash-and-Sign with Retry in the Quan- tum Random Oracle Model

2021, pp. 580–610 (cit. on p. 8). [KX24] Haruhisa Kosuge and Keita Xagawa. “Probabilistic Hash-and-Sign with Retry in the Quan- tum Random Oracle Model”. In:Public-Key Cryptography – PKC 2024. 2024, pp. 259– 288 (cit. on p. 8). [LR13] Troy Lee and Jérémie Roland. “A strong direct product theorem for quantum query complexity”. In:computational complexity22...

arXiv 2021

[4] [6]

Lemma A.6(Hybrid Security of Salted Game against Classical Advice).Let𝒢be a multi-output𝑘- search game (as defined in Def

The winning relation is defined as𝑅 𝐺,𝑐𝑕 :=𝑅 𝐻𝑖,𝑐𝑕𝑖; We will denote by𝜖𝒢𝑠(𝑞, 𝑐)the maximum probability over all𝑞-quantum and𝑐-classical hybrid algorithms 𝒜of winning the salted game𝒢 𝑠. Lemma A.6(Hybrid Security of Salted Game against Classical Advice).Let𝒢be a multi-output𝑘- search game (as defined in Def. 5.1), specified by a relation𝑅. Let𝒢 𝑠 be the sa...

[5] [2021]

The bitcoin backbone proto- col: Analysis and applications

2021, pp. 637–667 (cit. on p. 8). [GKL15] Juan A Garay, Aggelos Kiayias, and Nikos Leonardos. “The bitcoin backbone proto- col: Analysis and applications”. In:Journal of the ACM(2015) (cit. on pp. 8, 36). [HLS24] Yassine Hamoudi, Qipeng Liu, and Makrand Sinha. “The NISQ Complexity of Col- lision Finding”. In:Advances in Cryptology – EUROCRYPT 2024: 43rd A...

2021

[6] [2022]

Tight Characterizations for Preprocess- ing against Cryptographic Salting

2022, pp. 677–706 (cit. on pp. 8, 9). [DLW24] Fangqi Dong, Qipeng Liu, and Kewen Wu. “Tight Characterizations for Preprocess- ing against Cryptographic Salting”. In:Annual International Cryptology Conference. Springer. 2024 (cit. on pp. 6, 7, 35). [GHHM21] Alex B. Grilo, Kathrin Hövelmanns, Andreas Hülsing, and Christian Majenz. “Tight Adaptive Reprogramm...

2022