Open quantum query-complexity gaps for hidden-graph learning and combinatorial group testing: time-efficient optimal group testing, copy complexity of graph-state family identification, and the power of parity versus Bell-sampling access

Montanaro and Shao (arXiv:2011.08611) studied quantum algorithms for learning a hidden graph from OR queries and, via Bell sampling on graph states, from parity-type quantum measurements, proving near-optimal bounds for structured graph families and for combinatorial group testing. The single open gap their paper explicitly poses — the polynomial gap between the $\Omega(\sqrt{m})$ lower bound and the $\widetilde{O}(m^{3/4})$ upper bound for learning matchings and Hamiltonian cycles — was subsequently closed up to logarithmic factors by Ferber and Hardiman (arXiv:2402.18714), who learn matchings with $\widetilde{O}(\sqrt{m})$ OR queries. The open components are: (i) a time-efficient (polylog-overhead-free) quantum algorithm for combinatorial group testing matching Belovs' query-optimal $\Theta(\sqrt{d})$ bound, where $d$ is the number of defective items; (ii) the optimal copy complexity, as a function of the family size $|\mathcal{S}|$ , for identifying an unknown graph state from a finite candidate family; (iii) a precise characterization of which parity-query advantages survive when coherent parity access is weakened to random Bell samples; and (iv) whether the polylogarithmic factors in these learning algorithms are necessary.

Background

In the hidden-graph learning problem, an unknown graph $G$ on $n$ vertices with $m$ edges must be reconstructed from queries. An OR query, specified by a vertex subset $S$ , asks whether $G$ has at least one edge with both endpoints in $S$ ; it models the natural experiment of pooling items and testing whether the pool contains a defective item, as in combinatorial group testing (CGT), where at most $d$ of $n$ items are defective and a pooled test reveals whether a queried subset contains any defective. On a quantum computer each query may be made in superposition, and quantum search (Grover-type amplitude amplification) often reduces the number of queries polynomially. A second access model studied by Montanaro and Shao uses graph states: a graph state $|G\rangle$ is the stabilizer quantum state (a quantum state specified by the group of Pauli operators that fix it) obtained by preparing $|+\rangle^{\otimes n}$ , where $|+\rangle=(|0\rangle+|1\rangle)/\sqrt{2}$ , and applying a controlled-Z gate (which applies a phase of $-1$ to $|11\rangle$ ) on each edge of $G$ . Bell sampling — jointly measuring each of the $n$ corresponding qubit pairs of $|G\rangle^{\otimes 2}$ in the Bell basis (the basis of maximally entangled two-qubit states) — returns, per sample, a uniformly random subset of the vertices together with the parities of its intersections with every row of the adjacency matrix of $G$ , so Bell sampling emulates parity queries restricted to random subsets, without needing coherent control of which subset is queried. A parity query, by contrast, lets the algorithm choose any subset $S$ and receive the parity of the number of edges with both endpoints in $S$ , a strictly stronger oracle. Montanaro and Shao (TQC 2022; arXiv:2011.08611) gave quantum OR-query algorithms learning Hamiltonian cycles, matchings, and constant-degree graphs in $\widetilde{O}(m^{3/4})$ queries (writing $\widetilde{O}(\cdot)$ for bounds up to polylogarithmic factors); the best lower bound is $\Omega(\sqrt{m})$ , due to Ambainis and Montanaro (arXiv:1210.1148) via reduction from CGT. They connected CGT to Belovs' result for symmetric juntas — Boolean functions that depend only on their Hamming weight once restricted to an unknown set of relevant variables (arXiv:1311.6777) — proved via the adversary bound, a spectral method that characterizes quantum query complexity exactly: the quantum query complexity of CGT with at most $d$ defectives is $\Theta(\sqrt{d})$ , but the optimal algorithm may not be time-efficient. Montanaro and Shao instead give an efficiently implementable algorithm, built from the gapped group-testing algorithm of Ambainis, Belovs, Regev, and de Wolf (arXiv:1507.03126), at the cost of an $O(\log d\log\log d)$ factor, i.e. $O(\sqrt{d}\log d\log\log d)$ queries. For graph states they proved (Theorem 12) that $O(\log|\mathcal{S}|)$ copies suffice to identify an unknown element of any finite family $\mathcal{S}$ of graph states by Bell sampling, noted lower bounds of $\Omega((\log|\mathcal{S}|)/n)$ from Holevo's theorem (which caps the classical information extractable from $n$ qubits), and observed that the family of all graphs on $r$ vertices requires $\Theta(r)$ copies, suggesting the best achievable dependence might be $O(\sqrt{\log|\mathcal{S}|})$ . They also proved structural separations between the models: two parity queries reveal an entire row of the adjacency matrix (their Lemma 16), while in the graph-state (Bell-sampling) model even one entry of an arbitrary row requires $\Omega(n)$ copies. In 2024, Ferber and Hardiman (arXiv:2402.18714) resolved the headline polynomial gap: they learn a matching with $O(\sqrt{m}\log m\log^{11/2} n)$ OR queries and any graph of maximum degree $\Delta$ with $O(\Delta\sqrt{m}\log(m/\Delta)\log^{11/2} n)$ OR queries, removing the constant-colorability restriction, using Vizing's theorem (any graph of maximum degree $\Delta$ has its edges partitionable into at most $\Delta+1$ matchings) plus a quantum group-testing subroutine and concentration bounds. This leaves the logarithmic factors, the time-efficiency question, the copy-complexity question, and the model-characterization question open.

Problem Statement

The problem comprises four open components, each an independent open question, sharing one objective — pinning the exact quantum query and copy complexity of the hidden-graph learning and combinatorial group testing tasks introduced by Montanaro and Shao, and the relative power of the OR-query, parity-query, and Bell-sampling access models. After the Ferber–Hardiman resolution of the polynomial part of the original OR-query gap, the components that remain open are: (1) Time-efficient optimal group testing: construct a quantum algorithm for combinatorial group testing — identifying an unknown set of at most $d$ defective items among $n$ items, where a query is an OR test on an arbitrary subset of the items — that uses the query-optimal $\Theta(\sqrt{d})$ queries of Belovs' adversary bound while also running in time polynomial in $n$ ; equivalently, remove the $O(\log d\log\log d)$ overhead of the known efficient implementation. (2) Copy complexity of family identification: determine the optimal dependence on the family size $|\mathcal{S}|$ of the number of copies of an unknown graph state needed to identify it from a finite family $\mathcal{S}$ — the truth lies between $\Omega((\log|\mathcal{S}|)/n)$ and $O(\log|\mathcal{S}|)$ , with $O(\sqrt{\log|\mathcal{S}|})$ suggested for natural families; either exhibit a family where $\log|\mathcal{S}|$ (up to constants) copies are necessary, or give an improved measurement scheme. (3) Model characterization: for each hidden-graph learning task considered by Montanaro–Shao (learning Hamiltonian cycles, matchings, and bounded-degree graphs, and combinatorial group testing), determine whether the best known parity-query upper bounds remain achievable in the graph-state (Bell-sampling) model — in which Bell sampling supplies parity queries only on uniformly random subsets — or whether coherent parity queries on algorithm-chosen subsets are provably stronger for that task, beyond the known separation that two parity queries reveal an entire adjacency row while one arbitrary entry needs $\Omega(n)$ Bell-sampled copies. (4) Logarithmic overheads: for the algorithms above and for the majority/exact-half learning problems of Montanaro–Shao — learning the hidden set of $k$ relevant variables of a function $f:\{0,1\}^n\to\{0,1\}$ promised to equal a known function $g$ on that set, where $g$ is the majority function ( $g(x)=1$ iff $|x|\geq k/2$ ) or the exact-half function ( $g(x)=1$ iff $|x|=k/2$ , with $k$ even), for which the known time-efficient algorithm uses $O(k^{1/4}\log k)$ queries versus Belovs' query-optimal $O(k^{1/4})$ — either remove the polylogarithmic factors (e.g. achieve $O(\sqrt{m})$ OR queries for matchings, or $O(\Delta\sqrt{m})$ for max-degree- $\Delta$ graphs, with no log factors; these bounds are illustrative instances of the general demand, not its sole target) or prove lower bounds showing some logarithmic factor is necessary. Each of the four components is posed as an independent open question: a rigorous resolution of any single component constitutes a valid solution to the task, and resolving additional components is welcome.

References

Ashley Montanaro, Changpeng Shao, "Quantum algorithms for learning a hidden graph and beyond", arXiv:2011.08611 (2020; published as "Quantum Algorithms for Learning a Hidden Graph", TQC 2022, LIPIcs, DOI 10.4230/LIPIcs.TQC.2022.1), https://arxiv.org/abs/2011.08611, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.1
Asaf Ferber, Liam Hardiman, "A quantum algorithm for learning a graph of bounded degree", arXiv:2402.18714 (2024), https://arxiv.org/abs/2402.18714
Aleksandrs Belovs, "Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound", arXiv:1311.6777 (2013), https://arxiv.org/abs/1311.6777
Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf, "Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing", arXiv:1507.03126 (2015), https://arxiv.org/abs/1507.03126
Andris Ambainis, Ashley Montanaro, "Quantum algorithms for search with wildcards and combinatorial group testing", Quantum Information and Computation 14(5&6), 2014, arXiv:1210.1148, https://arxiv.org/abs/1210.1148
Yingkai Ouyang, Marco Tomamichel, "Learning quantum graph states with product measurements", arXiv:2205.06432 (2022), https://arxiv.org/abs/2205.06432
Xiaowei Huang, Shihao Zhang, Lvzhou Li, "Quantum Algorithms for Identifying Hidden Strings with Applications to Matroid Problems", arXiv:2211.10667 (2022), https://arxiv.org/abs/2211.10667
Nikhil S. Mande, Swagato Sanyal, Viktor Zamaraev, "Complexity of learning matchings and half graphs via edge queries", arXiv:2507.03151 (2025), https://arxiv.org/abs/2507.03151