pith. machine review for the scientific record. sign in

arxiv: 2604.07954 · v1 · submitted 2026-04-09 · 🪐 quant-ph · cs.CC· cs.DS

Recognition: 2 theorem links

· Lean Theorem

Quantum Property Testing for Bounded-Degree Directed Graphs

Pan Peng , Jingyu Wu
Authors on Pith no claims yet

Pith reviewed 2026-05-10 17:47 UTC · model grok-4.3

classification 🪐 quant-ph cs.CCcs.DS
keywords quantum property testingdirected graphsbounded degreeunidirectional modelsubgraph approximationquery complexityquantum speedup
0
0 comments X

The pith

Any property testable with constant classical bidirectional queries on bounded-degree directed graphs can be tested with n to the power 1/2 minus Omega(1) quantum unidirectional queries.

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

The paper shows how to convert any constant-query classical tester that works when both incoming and outgoing edges are accessible into a quantum tester that works when only outgoing edges are accessible. The resulting quantum algorithm uses n raised to a power strictly less than one-half queries, which is an almost quadratic improvement over the best known classical unidirectional algorithms. The authors also prove that this improvement is nearly the best possible by exhibiting one explicit property that still needs nearly square-root many quantum queries even after the conversion. As a direct consequence, the number of copies of any fixed small subgraph can be approximated to additive error delta n with o(sqrt(n)) quantum queries.

Core claim

For directed graphs with constant maximum in- and out-degree, every property that admits a constant-query tester in the classical bidirectional model also admits a tester in the quantum unidirectional model whose query complexity is n to the power 1/2 minus Omega of epsilon and d. The transformation is obtained by using coherent superposition queries to outgoing neighbors to simulate the missing incoming-neighbor information. The same paper supplies a matching lower bound: there exists an explicit property P_ε that is constant-query testable bidirectionally yet requires Omega-tilde of n to the power 1/2 minus f-prime of epsilon quantum unidirectional queries, where f-prime approaches zero as

What carries the argument

A general transformation that converts a classical bidirectional tester into a quantum unidirectional tester by replacing each bidirectional query with a coherent superposition query over outgoing neighbors, together with an explicit lower-bound construction for a property P_ε.

If this is right

  • Any graph property known to have a constant-query classical bidirectional tester immediately inherits a sublinear quantum unidirectional tester.
  • The number of occurrences of any constant-size directed subgraph H can be approximated to additive error delta n with o(sqrt(n)) quantum queries in the unidirectional model.
  • The gap between classical and quantum query complexity in the unidirectional model is almost quadratic for some properties.
  • Classical unidirectional testers that previously required Theta(sqrt(n)) queries can now be replaced by quantum testers with strictly fewer queries whenever the property also has a constant-query bidirectional tester.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar speedups may exist for undirected graphs or for properties that require more than constant classical queries.
  • The technique could be adapted to other oracles that give only one direction of information, such as one-way functions in cryptography.
  • It raises the question whether the same almost-quadratic separation holds for testing properties of hypergraphs or higher-order structures.

Load-bearing premise

The classical bidirectional tester must exist and the quantum model must allow coherent superposition queries to the list of outgoing neighbors of any vertex.

What would settle it

An explicit construction of a property that admits an O(1)-query classical bidirectional tester yet requires Omega(sqrt(n)) quantum unidirectional queries, or a concrete quantum algorithm that solves P_ε with o(n^{1/2 - c}) queries for some positive c.

Figures

Figures reproduced from arXiv: 2604.07954 by Jingyu Wu, Pan Peng.

Figure 1
Figure 1. Figure 1: As shown on the left, Γ and Γ′ are rooted directed graphs with i = 3 and i ′ = 5 edges respectively (the red vertices v and v ′ are marked as roots respectively). On the right, we depict a tree of depth i, where each node at depth j corresponds to a tuple in the set WΓ[j] ,Γ′. An edge between W1 and W2 exists if and only if there exists some edge e such that W1 × e = W2. Tuples enclosed in the same circle … view at source ↗
Figure 2
Figure 2. Figure 2: Illustration on how the events defined above depend on each other. The black, purple, [PITH_FULL_IMAGE:figures/full_fig_p021_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration on how events depend on each other defined in Definition 4.6 when [PITH_FULL_IMAGE:figures/full_fig_p029_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: We choose δi properly, such that all intervals [β δi Γ , α δi Γ ] are disjoint. Therefore, in each row, at most one element equals ∗ (marked as pink), and the other elements equal 0 or 1 (marked as green). That means that there are at most Dd,q (abbreviated as D in the figure) non-all-green columns, which is only 1% of all columns. 4.5 Proof of central properties To prove Claim 4.7 and Claim 4.8, we need t… view at source ↗
read the original abstract

We study quantum property testing for directed graphs with maximum in-degree and out-degree bounded by some universal constant $d$. For a proximity parameter $\varepsilon$, we show that any property that can be tested with $O_{\varepsilon,d}(1)$ queries in the classical bidirectional model, where both incoming and outgoing edges are accessible, can also be tested in the quantum unidirectional model, where only outgoing edges are accessible, using $n^{1/2 - \Omega_{\varepsilon,d}(1)}$ queries. This yields an almost quadratic quantum speedup over the best known classical algorithms in the unidirectional model. Moreover, we prove that our transformation is almost tight by giving an explicit property $P_\varepsilon$ that is $\varepsilon$-testable within $O_\varepsilon(1)$ classical queries in the bidirectional model, but requires $\widetilde{\Omega}(n^{1/2-f'(\varepsilon)})$ quantum queries in the unidirectional model, where $f'(\varepsilon)$ is a function that approaches $0$ as $\varepsilon$ approaches $0$. As a byproduct, we show that in the unidirectional model, the number of occurrences of any constant-size subgraph $H$ can be approximated up to additive error $\delta n$ using $o(\sqrt{n})$ quantum queries.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript studies quantum property testing for directed graphs with maximum in- and out-degree bounded by a constant d. It claims that any property testable with O_{ε,d}(1) classical queries in the bidirectional model can be tested using n^{1/2 - Ω_{ε,d}(1)} quantum queries in the unidirectional model (only outgoing edges accessible via superposition). It provides an almost-matching lower bound via an explicit property P_ε requiring Ω̃(n^{1/2 - f'(ε)}) quantum queries (with f'(ε) → 0 as ε → 0), and as a byproduct shows that the number of occurrences of any constant-size subgraph H can be approximated to additive error δn using o(√n) quantum queries.

Significance. If the central reduction and lower-bound construction hold, the work gives a general method for lifting constant-query classical bidirectional testers to sublinear-query quantum unidirectional testers, yielding an almost-quadratic speedup over known classical unidirectional algorithms. The explicit dependence on ε and d, the nearly tight lower bound, and the subgraph-approximation byproduct are all strengths; the latter is of independent interest for quantum graph algorithms.

major comments (2)
  1. [§3] §3 (Reduction): the claimed n^{1/2 - Ω_{ε,d}(1)} bound requires that the error introduced by the quantum simulation of the classical bidirectional tester (via superposition access to out-neighbors) remains controlled after O(1) classical queries; the manuscript must show explicitly that the failure probability and additive error do not accumulate to erase the Ω(1) term in the exponent.
  2. [§5] §5 (Lower bound for P_ε): the Ω̃(n^{1/2 - f'(ε)}) quantum lower bound is stated to be almost tight, but the construction must verify that the distinguishing advantage in the unidirectional quantum model is indeed Ω(1) for the chosen family of graphs; if the reduction from the classical bidirectional tester to the quantum case introduces even a small extra factor, the f'(ε) term may vanish.
minor comments (2)
  1. [Abstract] Abstract: the function f'(ε) is introduced without even a qualitative description of its decay rate; a single sentence clarifying that f'(ε) = o(1) but positive for fixed ε > 0 would improve readability.
  2. [Byproduct result] Byproduct theorem: the o(√n) query bound for subgraph counting should state the dependence on δ and on the size of H (even if only polylog factors); the current statement leaves the reader uncertain whether the bound remains sublinear when δ is inverse-polynomial.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We are grateful to the referee for the thorough review and valuable suggestions. Below we provide point-by-point responses to the major comments. We will revise the manuscript accordingly to address the concerns raised.

read point-by-point responses

  1. Referee: [§3] §3 (Reduction): the claimed n^{1/2 - Ω_{ε,d}(1)} bound requires that the error introduced by the quantum simulation of the classical bidirectional tester (via superposition access to out-neighbors) remains controlled after O(1) classical queries; the manuscript must show explicitly that the failure probability and additive error do not accumulate to erase the Ω(1) term in the exponent.

    Authors: We acknowledge that the control of simulation errors is crucial for maintaining the exponent in the query complexity bound. Upon re-examination, our proof in Section 3 bounds the error per simulation step, but we agree it could be made more explicit. In the revised manuscript, we will include a lemma that quantifies the total error after O(1) queries: the failure probability is at most O(1/n) by choosing appropriate precision in the quantum simulation, and additive errors are at most ε/3, which does not impact the Ω_{ε,d}(1) term since it is independent of n. This preserves the claimed bound. revision: yes

  2. Referee: [§5] §5 (Lower bound for P_ε): the Ω̃(n^{1/2 - f'(ε)}) quantum lower bound is stated to be almost tight, but the construction must verify that the distinguishing advantage in the unidirectional quantum model is indeed Ω(1) for the chosen family of graphs; if the reduction from the classical bidirectional tester to the quantum case introduces even a small extra factor, the f'(ε) term may vanish.

    Authors: Thank you for this observation. The lower bound construction in Section 5 is based on a family where the bidirectional classical tester has constant advantage, and our reduction to the unidirectional quantum model incurs only a constant factor loss in the advantage (due to the specific choice of parameters in P_ε that make f'(ε) absorb any logarithmic or constant losses). We will add a paragraph in the revised version explicitly computing the distinguishing probability in the quantum unidirectional setting, confirming it remains Ω(1) for the hard instances, thus keeping the lower bound almost tight as stated. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes a general reduction showing that any constant-query classical bidirectional tester for bounded-degree directed graphs lifts to a sublinear-query quantum unidirectional tester, plus an explicit almost-matching lower bound via a specific property P_ε and a subgraph-counting byproduct. These claims rest on standard quantum oracle access (superposition queries to out-neighbors) and classical property-testing machinery without any self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations that collapse the query bounds to the paper's own inputs. The abstract and described results are self-contained against external benchmarks in quantum query complexity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard definitions of the bidirectional and unidirectional graph oracles, the bounded-degree assumption, and the usual quantum query model; no new free parameters or invented entities are introduced.

axioms (2)
  • domain assumption Bounded in- and out-degree d is a fixed constant independent of n
    Invoked throughout the statement of both the upper and lower bounds.
  • standard math Quantum queries may be performed in superposition over outgoing neighbors
    Standard quantum query model used for the unidirectional tester.

pith-pipeline@v0.9.0 · 5522 in / 1416 out tokens · 41818 ms · 2026-05-10T17:47:16.946365+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

10 extracted references · 2 canonical work pages

  1. [1]

    Learning-graph-based quantum algorithm for k-distinctness

    [Bel12] Aleksandrs Belovs. Learning-graph-based quantum algorithm for k-distinctness. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 207– 216,

    2012

  2. [2]

    Every minor-closed property of sparse graphs is testable

    [BSS08] Itai Benjamini, Oded Schramm, and Asaf Shapira. Every minor-closed property of sparse graphs is testable. In40th Annual ACM Symposium on Theory of Computing, STOC 2008, pages 39–44,

    2008

  3. [3]

    Testable properties in general graphs and random order streaming

    [CFPS20] Artur Czumaj, Hendrik Fichtenberger, Pan Peng, and Christian Sohler. Testable properties in general graphs and random order streaming. In Jaroslaw Byrka and Raghu Meka, editors,Approximation, Randomization, and Combinatorial Optimiza- tion. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference, volume 176 ofLIPIcs,...

    2020

  4. [4]

    A note on the quantum query complexity of permutation symmetric functions

    [Cha19] Andr´ e Chailloux. A note on the quantum query complexity of permutation symmetric functions. InITCS 2019-10th Annual Innovations in Theoretical Computer Science,

    2019

  5. [5]

    [Fis24] Eldar Fischer

    Association for Computing Machinery. [Fis24] Eldar Fischer. A basic lower bound for property testing.arXiv preprint arXiv:2403.04999,

    work page arXiv

  6. [6]

    Computing and testing small connectivity in near- linear time and queries via fast local cut algorithms

    [FNY+20] Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, and Sor- rachai Yingchareonthawornchai. Computing and testing small connectivity in near- linear time and queries via fast local cut algorithms. InProceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2046–2065. SIAM,

    2046

  7. [7]

    [Gro96] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Gary L. Miller, editor,Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 212–219. ACM,

    1996

  8. [8]

    A note on the sign degree of formulas.arXiv preprint arXiv:0909.4607,

    [Lee09] Troy Lee. A note on the sign degree of formulas.arXiv preprint arXiv:0909.4607,

    work page arXiv

  9. [9]

    On finding quantum multi-collisions

    56 [LZ19] Qipeng Liu and Mark Zhandry. On finding quantum multi-collisions. In Yuval Ishai and Vincent Rijmen, editors,Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part III, volume 11478 ofLecture Notes in Compute...

    2019

  10. [10]

    An optimal separation between two property testing models for bounded degree directed graphs

    [PW23] Pan Peng and Yuyang Wang. An optimal separation between two property testing models for bounded degree directed graphs. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors,50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, volume 261 ofLIPIcs, pages 96:1–96:16. Schloss ...

    2023