Pith. sign in

REVIEW 4 major objections 3 minor 27 references

Optimal quantum sampling on distributed databases

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

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

Pith's one-line read This paper proves that distributed quantum sampling can be done with $O(n\sqrt{\nu N/M})$ sequential queries and $O(\sqrt{\nu N/M})$ parallel queries, and that both bounds are optimal in the oblivious communication model.

desk verdict The distributed sampling model and the D-operator algorithm are new and sound, but the claimed optimality lower bound is false as stated; a single-machine Grover counterexample breaks it. read the letter →

arxiv 2506.07724 v1 pith:DPHBJXZH submitted 2025-06-09 quant-ph cs.DC

Longyun Chen , Jingcheng Liu , Penghui Yao This is my paper
classification quant-phcs.DC MSC 68Q1281P68
keywords quantumsamplingdistributeddatabasesquerycomplexityobliviouscommunicationmodelamplitudeamplificationGroveroracleadversarymethodsequentialandparallelqueries
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 starts the study of quantum sampling in a distributed setting: a coordinator must prepare the state $\frac{1}{\sqrt{M}}\sum_{i}\sqrt{c_i}|i\rangle$ for a database split across $n$ machines, where each machine only answers simple multiplicity queries. Its main results are matching upper and lower bounds: $O(n\sqrt{\nu N/M})$ sequential queries and $O(\sqrt{\nu N/M})$ parallel queries, both optimal among oblivious protocols. The algorithms let each machine act as a local Grover oracle, combine the oracles into one distributing operator, and then run zero-error amplitude amplification; the optimality proof uses an adversary-style potential that grows as queries reveal one machine's support. If the paper is right, distributing a database does not change the essential quantum cost of sampling: the same square-root barrier appears, and the sequential model pays only an extra factor of $n$ that simultaneous queries remove.

What carries the argument

The central object is the distributing operator $D$, defined by $D|i,0\rangle = \sqrt{c_i/\nu}\,|i,0\rangle + \sqrt{(\nu-c_i)/\nu}\,|i,1\rangle$, which maps the uniform state to a superposition whose target amplitude is $\sqrt{M/(\nu N)}$. Each machine implements a local oracle $O_j|i,s\rangle = |i,(s+c_{ij}) \bmod (\nu+1)\rangle$, and these oracles are composed to realize $D$ with $2n$ sequential queries or $4$ parallel queries. The same operator carries both directions: amplitude amplification over $D$ gives the upper bounds, while the lower bound analyzes the potential $D_t = \mathbb{E}_{T\in\mathcal{T}}\|\,|\psi^T_t\rangle - |\psi_t\rangle\,\|^2$, the expected separation between the algorithm's state on hard inputs $T$ and its state when machine $k$ is empty.

What would settle it

Exhibit an oblivious distributed quantum sampling algorithm that uses $o(n\sqrt{\nu N/M})$ sequential queries or $o(\sqrt{\nu N/M})$ parallel queries while preparing a state with fidelity above $9/16$ on the hard-input family of Definition 5.4. If such a protocol exists, the claimed optimality is false; if not, the remaining test is whether a new hard distribution can cover the sparse regime where the current hard-input condition fails.

Watch

Extended reading notes

Core claim

On its own terms, the paper's discovery is a pair of tight query-complexity bounds for distributed quantum sampling in the oblivious communication model, where the order of queries is fixed in advance. It constructs a sequential algorithm making $O(n\sqrt{\nu N/M})$ oracle calls and a parallel algorithm making $O(\sqrt{\nu N/M})$ simultaneous oracle calls, each preparing the sampling state with zero error under the stated parameter condition. It then proves matching lower bounds of $\Omega(\sum_j \sqrt{\kappa_j N/M})$ for sequential protocols and $\Omega(\max_j \sqrt{\kappa_j N/M})$ for parallel protocols, where $\kappa_j$ is the capacity of machine $j$, using hard inputs formed by permuting the support of a single machine's dataset. The authors read these bounds as showing that the fundamental barrier for distributed quantum sampling is the same as in the centralized setting, despite the extra constraints of distributed storage.

Load-bearing premise

The lower-bound proof assumes that, for the machine under analysis, one can find a hard input in which that machine holds a constant share of the total data and its elements appear on average at least a fixed fraction of the machine's capacity; when the total dataset is too small, no such input exists, so optimality is proven only outside that sparse regime.

Editorial extensions

If this is right

  • A coordinator can prepare the global sampling state from $n$ separate databases with $O(n\sqrt{\nu N/M})$ sequential oracle calls, and no oblivious sequential algorithm can do asymptotically better.
  • With simultaneous queries, the factor $n$ disappears: $O(\sqrt{\nu N/M})$ parallel queries suffice and are optimal in the oblivious parallel model.
  • The lower bounds apply even when all databases are disjoint, so the unavoidable cost reflects locating support across machines rather than duplicate storage.
  • Because the optimal query counts match the centralized square-root barrier up to the known parameters, adding a distributed architecture does not create a new essential quantum difficulty for sampling.

Reading between the lines

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

  • Beyond the paper: the oblivious assumption is doing load-bearing work; a direct next question is whether adaptive, non-oblivious communication can beat the sequential factor $n$, since the lower-bound potential relies on the query order being fixed in advance.
  • Beyond the paper: the oracle's local update property suggests the same algorithms can track dynamically changing databases with little recomputation, a direction the paper mentions but does not develop.
  • Beyond the paper: in the sparse regime where the hard-input condition of the lower bound fails (for instance when total data $M$ is tiny compared with $\nu N$), the tight complexity is not settled by these theorems, and the square-root barrier could be tested there.
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.

Referee Report

4 major / 3 minor

Summary. The paper introduces distributed quantum sampling in an oblivious communication model, where each machine maintains a multiplicity-counting oracle and a coordinator aims to prepare the quantum sampling state. It proposes a sequential algorithm using O(n sqrt(nu N/M)) queries and a parallel algorithm using O(sqrt(nu N/M)) parallel queries, and claims both are optimal via adversary-based lower bounds. The algorithmic constructions are elegant and appear correct as reductions to amplitude amplification. However, the central optimality claim is not supported: the lower bound proof relies on hard inputs that need not exist when the total database size M is small, and the advertised lower bound in terms of the public capacity nu is actually false in the sparse regime.

Significance. If the optimality claims were correct, the paper would establish a tight distributed analogue of the centralized quantum sampling barrier and give a clean model for distributed quantum databases. The upper-bound algorithms are simple, well-motivated, and correctly reduce the problem to amplitude amplification, which is a genuine strength. The adversarial lower bound is the main contribution, though, and it fails as stated: the proof cannot instantiate its hard inputs when M is small relative to nu, and a concrete single-marked-element instance admits a Grover-style algorithm with O(sqrt(N)) queries, contradicting the advertised Omega(nu N/M) lower bound. The result therefore does not establish optimality in the parameter regimes covered by the theorems.

major comments (4)
  1. [Section 5.2, Definition 5.4 and proof of Theorem 5.1] The hard-input condition (8) requires M_k/m_k >= beta*kappa_k. Since M_k <= M and m_k >= 1, every input satisfies M_k/m_k <= M. Thus, when M < beta*kappa_k, no input satisfies the hard-input condition. In the proof of Theorem 5.1, the assertion that for M < beta^2*kappa_k*N/16 one can 'put all of the elements to the k-th machine' to construct a hard input is false when kappa_k > 1/beta and M is small: putting all elements on machine k gives M_k/m_k = 1 only if all M elements are distinct, which is not >= beta*kappa_k. Consequently Lemma 5.7 cannot be instantiated, and equation (13) is unjustified.
  2. [Theorem 1.1 and abstract, optimality in terms of nu] The advertised lower bound Omega(sqrt(nu N/M)) is false as stated. Take n=1, N large, M=1, and nu=N, with the single machine storing one element i*. The target state is |i*>. The counting oracle O|i,s> = |i,(s+c_i) mod (nu+1)> allows the coordinator to compute c_i into an auxiliary register with one query, apply an input-independent phase flip on the condition c_i > 0, and uncompute with O^dagger. This simulates the standard Grover sign-flip oracle with two oracle calls per iteration, so |i*> can be prepared with constant fidelity using O(sqrt(N)) queries. The claimed lower bound would be Omega(sqrt(nu N/M)) = Omega(N), which is asymptotically larger.
  3. [Transition from kappa_j to nu in Theorem 5.1] Even if the formal lower bound in Theorem 5.1 is read as a bound in terms of the actual maximum multiplicities kappa_j, the statement 'For the case where kappa_j is unknown, we can just use nu for kappa_j' is invalid for a lower bound. Replacing kappa_j by a larger quantity nu strengthens the bound, and this strengthening is only legitimate if there exist inputs with kappa_j = Omega(nu). When M < nu, the actual maximum multiplicity on any machine is at most M, so no such input exists; the M=1 example above shows the strengthened bound is false.
  4. [Section 5.4, Theorem 5.2] The parallel lower bound inherits the same defect: Lemma 5.9 invokes the proof of Lemma 5.7, which requires hard inputs satisfying M_k/m_k >= beta*kappa_k. The same small-M obstruction applies, and the max_j Omega(sqrt(kappa_j N/M)) bound cannot be converted into the advertised max_j Omega(sqrt(nu N/M)) bound without an additional density assumption such as M = Omega(nu). No such assumption appears in the theorem statements or in Theorem 1.1.
minor comments (3)
  1. [Section 4, headings] The headings of Theorem 4.3 and Theorem 4.5 contain typos: 'seqential qeries' and 'qantum sampling with parallel qeries' should be 'sequential queries' and 'quantum sampling with parallel queries'.
  2. [Section 5 cross-references] Several cross-references are inconsistent: Definition 5.5 refers to 'Theorem 5.4' where Definition 5.4 is meant; Lemmas 5.6 and 5.7 refer to 'Theorem 5.5' instead of Definition 5.5; and Proposition C.1 refers to 'Theorem 5.6' instead of Lemma 5.6. The introductory paragraph of Section 5 also calls Lemma 5.7 and Lemma 5.8 'Theorem 5.7' and 'Theorem 5.8'.
  3. [Section 4.1, condition in Theorem 4.3] The condition nu >= M/(N*epsilon) in Theorem 4.3 is not discussed or motivated; if epsilon is the approximation parameter, it couples the allowed error with the database parameters in a way that deserves explanation, since the later lower bound does not impose this condition.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: algorithms and lower bounds are proved from external amplitude-amplification and adversary results, not from their own conclusions.

full rationale

The paper's upper bounds (Theorems 4.3 and 4.5) are self-contained reductions to the standard zero-error amplitude amplification of Brassard et al. [9], with the operator D implemented explicitly from the machine oracles in Lemmas 4.2 and 4.4; no parameter is fitted to the quantity being predicted. The lower bounds (Theorems 5.1 and 5.2) are adversary arguments using a potential function D_t, with the claimed query-count lower bound obtained by combining Lemmas 5.7 and 5.8 (and their parallel analogues), not by assuming the conclusion. The hard-input construction in the proof of Theorem 5.1 for the case M < beta^2 kappa_k N/16 is questionable when M is too small to satisfy M_k/m_k >= beta kappa_k, but this is a correctness gap about the existence of hard inputs, not circularity: the lower bound is not equivalent by construction to the hard-input condition. The cited external results (Zalka, Brassard et al., Ambainis) are standard and are not by the present authors, so no self-citation is load-bearing. Consequently, no circular step can be exhibited from the paper's own equations.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim relies on the oracle model, the oblivious communication model, and the existence of hard inputs with high average multiplicity. The last assumption is not stated explicitly and fails for sparse databases. No parameters are fitted to data.

assumptions (4)
  • domain assumption Each machine implements the counting oracle O_j|i,s> = |i,(s+c_ij) mod (nu+1)> with public capacity nu.
    Equation (1) defines the model; all algorithms and lower bounds operate with this oracle.
  • domain assumption The oblivious communication model: the sequence of queries is fixed independently of the input.
    Section 3 states this; the lower bound uses it to fix the unitary operators U_t.
  • ad hoc to paper A hard input exists for any parameters with M_k >= alpha M and M_k/m_k >= beta kappa_k for constants alpha and beta.
    Used in the proof of Theorem 5.1 to construct the adversary distribution; false when M is less than beta times kappa_k, for example M equals 1.
  • standard math Standard quantum mechanics, deferred measurement principle, and Uhlmann's theorem.
    Used in Lemma 5.3 and Appendix B.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal quantum sampling on distributed databases." pith.science (2026). https://pith.science/paper/DPHBJXZH

@misc{pith2026250607724,
  author       = {Pith},
  title        = {Pith review of: Optimal quantum sampling on distributed databases},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DPHBJXZH}},
  note         = {Machine review of arXiv:2506.07724}
}
read the original abstract

Quantum sampling, a fundamental subroutine in numerous quantum algorithms, involves encoding a given probability distribution in the amplitudes of a pure state. Given the hefty cost of large-scale quantum storage, we initiate the study of quantum sampling in a distributed setting. Specifically, we assume that the data is distributed among multiple machines, and each machine solely maintains a basic oracle that counts the multiplicity of individual elements. Given a quantum sampling task, which is to sample from the joint database, a coordinator can make oracle queries to all machines. We focus on the oblivious communication model, where communications between the coordinator and the machines are predetermined. We present both sequential and parallel algorithms: the sequential algorithm queries the machines sequentially, while the parallel algorithm allows the coordinator to query all machines simultaneously. Furthermore, we prove that both algorithms are optimal in their respective settings.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

27 extracted references · 9 canonical work pages

  1. [1]

    Rothblum

    Scott Aaronson and Guy N. Rothblum. 2019. Gentle measurement of quantum states and differential privacy. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing(Phoenix, AZ, USA)(STOC 2019). Association for Computing Machinery, New York, NY, USA, 322–333. https://doi.org/10.1145/3313276.3316378

    arXiv 2019

  2. [2]

    Dorit Aharonov and Amnon Ta-Shma. 2003. Adiabatic Quantum State Generation and Statistical Zero Knowledge. arXiv:quant-ph/0301023 [quant-ph] https://arxiv.org/abs/quant-ph/0301023

    arXiv 2003

  3. [3]

    Andris Ambainis. 2002. Quantum Lower Bounds by Quantum Arguments.J. Comput. System Sci.64, 4 (2002), 750–767. https://doi.org/10.1006/jcss.2002.1826

    arXiv 2002

  4. [4]

    Andris Ambainis, Loïck Magnin, Martin Roetteler, and Jeremie Roland. 2011. Symmetry-Assisted Adversaries for Quantum State Generation. In2011 IEEE 26th Annual Conference on Computational Complexity. IEEE, 167–177. https: //doi.org/10.1109/ccc.2011.24

    work page doi:10.1109/ccc.2011.24 2011

  5. [5]

    Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf

    Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf

    work page

  6. [6]

    Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, and Ronald de Wolf. 2021. Two new results about quantum exact learning.Quantum5 (Nov. 2021), 587. https://doi.org/10.22331/q-2021-11-24-587

    work page doi:10.22331/q-2021-11-24-587 2021

  7. [7]

    Srinivasan Arunachalam and Ronald De Wolf. 2018. Optimal quantum sample complexity of learning algorithms.J. Mach. Learn. Res.19, 1 (jan 2018), 2879–2878

    work page 2018

  8. [8]

    Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. 1998. Tight Bounds on Quantum Searching.Fortschritte der Physik46, 4-5 (jun 1998), 493–505. https://doi.org/10.1002/(sici)1521-3978(199806)46:4/5<493::aid-prop493>3.0.co;2-p

    doi:10.1002/(sici)1521-3978(199806)46:4/5 1998

Show all 27 references
  1. [9]

    Gilles Brassard, Peter Hø yer, Michele Mosca, and Alain Tapp. 2002. Quantum amplitude amplification and estimation. InQuantum computation and information (Washington, DC, 2000). Contemp. Math., Vol. 305. Amer. Math. Soc., Providence, RI, 53–74. https://doi.org/10.1090/conm/305/05215

    2002 doi

  2. [10]

    Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi. 2022. Near-optimal Quantum algorithms for multivariate mean estimation. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing(Rome, Italy)(STOC 2022). Association for Computing Machinery, New York, N...

    2022

  3. [11]

    András Gilyén and Tongyang Li. 2020. Distributional Property Testing in a Quantum World. In11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 151), Thomas Vidick (Ed.). Schloss Dagstuhl – Lei...

    2020 doi

  4. [12]

    Lov K. Grover. 1996. A fast quantum mechanical algorithm for database search. InProceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing(Philadelphia, Pennsylvania, USA)(STOC ’96). Association for Computing Machinery, New York, NY, USA, 212–219. https://doi...

    1996

  5. [13]

    Yassine Hamoudi. 2021. Quantum Sub-Gaussian Mean Estimator. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2021.50

    2021 doi

  6. [14]

    Yassine Hamoudi and Frédéric Magniez. 2019. Quantum Chebyshev’s Inequality and Applications. In46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Patras, Greece. https://doi.org/10.4230/LIPIcs. ICALP.2019.69

    2019 doi

  7. [15]

    Harrow, Avinatan Hassidim, and Seth Lloyd

    Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. 2009. Quantum Algorithm for Linear Systems of Equations. Phys. Rev. Lett.103 (Oct 2009), 150502. Issue 15. https://doi.org/10.1103/PhysRevLett.103.150502

    2009 doi

  8. [16]

    Yi-Lin Ju, I-Ming Tsai, and Sy-Yen Kuo. 2007. Quantum Circuit Design and Analysis for Database Search Applications. IEEE transactions on circuits and systems. I, Regular papers54, 11 (2007), 2552–2563

    2007

  9. [17]

    2022.Bounds on Oblivious Multiparty Quantum Communication Complexity

    François Le Gall and Daiki Suruga. 2022.Bounds on Oblivious Multiparty Quantum Communication Complexity. Springer International Publishing, 641–657. https://doi.org/10.1007/978-3-031-20624-5_39

    2022 doi

  10. [18]

    Reichardt, Robert Špalek, and Mario Szegedy

    Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy. 2011. Quantum Query Complexity of State Conversion. In2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. 344–353. https: //doi.org/10.1109/FOCS.2011.75

    2011 doi

  11. [19]

    Nathan Lindzey and Ansis Rosmanis. 2020. A Tight Lower Bound For Non-Coherent Index Erasure. In11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 151), Thomas Vidick (Ed.). Schloss Dagstuhl –...

    2020 doi

  12. [20]

    Hann, and Liang Jiang

    Junyu Liu, Connor T. Hann, and Liang Jiang. 2023. Data centers with quantum random access memory and quantum networks.Physical Review A108, 3 (Sept. 2023). https://doi.org/10.1103/physreva.108.032610

    2023 doi

  13. [21]

    Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha. 2011. Search via Quantum Walk.SIAM J. Comput.40, 1 (2011), 142–164. https://doi.org/10.1137/090745854 arXiv:https://doi.org/10.1137/090745854

    2011 doi

  14. [22]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang. 2011.Quantum Computation and Quantum Information: 10th Anniversary Edition(10th ed.). Cambridge University Press, USA

    2011

  15. [23]

    Maris Ozols, Martin Roetteler, and Jérémie Roland. 2013. Quantum rejection sampling.ACM Trans. Comput. Theory5, 3, Article 11 (aug 2013), 33 pages. https://doi.org/10.1145/2493252.2493256

    2013

  16. [24]

    Yaoyun Shi. 2002. Quantum lower bounds for the collision and the element distinctness problems. InThe 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.513–519. https://doi.org/10.1109/SFCS.2002. 1181975

    2002 doi

  17. [25]

    M. Szegedy. 2004. Quantum speed-up of Markov chain based algorithms. In45th Annual IEEE Symposium on Foundations of Computer Science. 32–41. https://doi.org/10.1109/FOCS.2004.53

    2004 doi

  18. [26]

    Pawel Wocjan and Anura Abeyesinghe. 2008. Speedup via quantum sampling.Phys. Rev. A78 (Oct 2008), 042336. Issue 4. https://doi.org/10.1103/PhysRevA.78.042336

    2008 doi

  19. [27]

    Í 𝑇∈T,𝑖∈𝑇 𝑘

    Christof Zalka. 1999. Grover’s quantum searching algorithm is optimal.Physical Review A60, 4 (oct 1999), 2746–2751. https://doi.org/10.1103/physreva.60.2746 A Proof of Lemma 5.3 By the assumption of the oblivious algorithm, the order of the oracles thatA makes is predeter- min...

    1999 doi

Pith tools

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