pith. sign in

arxiv: 2605.23442 · v1 · pith:JTXUC3H2new · submitted 2026-05-22 · 🪐 quant-ph · cs.DS

Ancilla-Efficient QSAMPLE Preparation for Reversible Markov Chains

Nicholas Zhao This is my paper

Pith reviewed 2026-05-25 04:48 UTC · model grok-4.3

classification 🪐 quant-ph cs.DS
keywords quantum samplingQSAMPLEreversible Markov chainsquantum signal processingamplitude amplificationancilla reductionSzegedy walkcooling schedule
0
0 comments X

The pith

A quantum algorithm prepares coherent samples from reversible Markov chains using only one ancilla qubit and inverse-square-root query scaling.

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

This paper introduces an end-to-end procedure to prepare QSAMPLEs, which are coherent encodings of stationary distributions of reversible Markov chains. The method requires only one ancilla qubit and works from an initial state plus oracle access, provided the user supplies lower bounds on state overlaps and phase gaps. It builds a selective phase compiler from a generalized quantum signal processing projector onto the 1-eigenspace of a qubitized Szegedy walk and embeds that compiler inside fixed-point amplitude amplification, then iterates across a cooling schedule. The resulting query complexity scales with the inverse square roots of the minimum overlap and minimum spectral gap, up to polylog factors, while producing a state within any target trace distance. This yields two concrete gains over prior work: ancilla count drops to one and the overlap dependence improves from linear inverse to square-root inverse.

Core claim

Given an initial state, oracle access, lower bounds on the overlaps between adjacent states, and lower bounds on the phase gaps, the algorithm outputs a QSAMPLE within any desired trace distance. The query complexity scales as the inverse square root of the minimum overlap and minimum spectral gap of the Markov chains across the cooling schedule, up to polylogarithmic factors, while using only one ancilla qubit in the working register.

What carries the argument

A selective phase compiler circuit using one ancilla qubit, constructed via a GQSP-based projector onto the 1-eigenspace of the qubitized Szegedy walk and inserted into the fixed-point amplitude amplification procedure.

If this is right

  • The working-register ancilla cost is reduced to one qubit.
  • The QSAMPLE transport overlap dependence improves from inverse minimum overlap to inverse square-root minimum overlap relative to the prior Grover pi-over-three fixed-point method.
  • A rigorous complexity analysis is obtained for preparing a Gibbs QSAMPLE as a direct application.
  • The framework supports any desired trace distance by adjusting the iteration count in the amplitude amplification loop.

Where Pith is reading between the lines

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

  • Hardware implementations of quantum sampling could become feasible on devices with severely limited ancilla resources.
  • The selective phase compiler technique may transfer to other quantum walk algorithms that need controlled phase operations without extra qubits.
  • Simulations of the qubit and query scaling versus trace distance provide a practical benchmark for comparing against earlier methods on concrete chains.

Load-bearing premise

The procedure assumes the user can supply lower bounds on the minimum overlap between adjacent states and on the minimum phase gap of the Markov chains.

What would settle it

Implement the algorithm on a small, explicitly diagonalizable reversible Markov chain with known stationary distribution and verify whether the output state reaches the claimed trace distance to the target QSAMPLE within the predicted number of queries.

Figures

Figures reproduced from arXiv: 2605.23442 by Nicholas Zhao.

Figure 1
Figure 1. Figure 1: Structure of the GQSP-based selective-phase compiler [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Architecture of the constant-ancilla QSAMPLE preparation algorithm. Top row: the cooling schedule advances through ℓ stages of stationary states |π0⟩ → · · · → |πℓ⟩. Bottom row: each transition |πei⟩ → |πei+1⟩ uses the qubitized Szegedy walk, to build a GQSP-based selective-phase compiler, to then use FPAA subroutine to transport the state. Denote pmin := min0≤i≤ℓ−1 pi and ∆min := min0≤i≤ℓ ∆Wi . Assume |π0… view at source ↗
Figure 3
Figure 3. Figure 3: Fixed-benchmark comparison of the resource cost of our [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
read the original abstract

Preparing quantum samples (QSAMPLES), coherent encodings of stationary distributions of reversible Markov chains, is a fundamental primitive in quantum sampling, particularly for quantum simulated annealing. A central limitation of existing phase-estimation-based frameworks is the ancilla qubit overhead. In this work, we present a new end-to-end framework requiring only one ancilla qubit in the working register. The key technical ingredient is a selective phase compiler circuit using one ancilla qubit, built from a generalized quantum signal processing (GQSP)-based projector onto the 1-eigenspace of the qubitized Szegedy walk. Embedding these selective phase compilers into the fixed-point amplitude amplification (FPAA) procedure and iterating yields a quantum algorithm that, given an initial state, oracle access, lower bounds on the overlaps between adjacent states, and lower bounds on the phase gaps, outputs a QSAMPLE within any desired trace distance and thus total variation distance. The query complexity scales inversely with the square roots of both the minimum overlap and the minimum spectral gap of the Markov chains across the cooling schedule, up to polylogarithmic factors. We also perform simulations to verify how our qubit and query complexity evolve with the trace distance, and how this work compares to the previous framework. These results establish two improvements over the previous framework by Wocjan and Abeyesinghe. First, the working-register ancilla cost is reduced to one. Second, by inserting our GQSP-based selective phase compiler into the FPAA procedure, we improve the QSAMPLE transport overlap dependence from inverse minimum overlap to inverse square-root minimum overlap, relative to their Grover pi-over-three fixed-point method. Finally, as a direct application, we apply the quantum algorithm to prepare a Gibbs QSAMPLE and obtain a rigorous complexity analysis.

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 / 3 minor

Summary. The manuscript presents an end-to-end quantum algorithm for preparing QSAMPLES (coherent encodings of stationary distributions) of reversible Markov chains. It requires only one ancilla qubit by constructing a GQSP-based selective phase compiler that projects onto the 1-eigenspace of the qubitized Szegedy walk, then embedding this compiler inside fixed-point amplitude amplification (FPAA). Given an initial state, oracle access, and supplied lower bounds on minimum state overlaps and phase gaps across a cooling schedule, the algorithm outputs a QSAMPLE to arbitrary trace distance (hence total variation distance). The query complexity scales as the inverse square root of the minimum overlap and minimum spectral gap (up to polylog factors). The work claims two improvements over Wocjan and Abeyesinghe: reduction to one working-register ancilla and replacement of their linear overlap dependence with square-root dependence. Simulations are provided to track qubit and query costs versus target trace distance, and the framework is applied to Gibbs-state preparation with a rigorous complexity bound.

Significance. If the central construction is correct, the result meaningfully lowers the ancilla overhead for quantum sampling primitives and improves the overlap scaling, both of which are practically relevant for quantum simulated annealing and related algorithms on hardware with limited qubit resources. The explicit treatment of supplied lower bounds on overlaps and gaps as inputs, together with the simulation verification and the Gibbs-state application, strengthens the contribution.

major comments (2)
  1. [Section 3 (GQSP projector and selective phase compiler)] The one-ancilla claim and the sqrt-overlap improvement both rest on the GQSP-based selective phase compiler inside FPAA. The manuscript should supply an explicit resource count (qubit and gate) for this compiler, including how the projector is realized without additional ancillae beyond the stated single qubit (see the construction around the qubitized Szegedy walk).
  2. [Section 4 (complexity analysis)] The final query complexity is stated to be O(1/sqrt(delta_min * gamma_min) * polylog(1/epsilon)). The error-propagation analysis that converts the supplied lower bounds and the FPAA iteration count into this scaling (including the precise polylog factors) should be written out with explicit constants or big-O derivations rather than summarized.
minor comments (3)
  1. [Abstract and Section 1] The abstract and introduction use “QSAMPLE” and “GQSP” before defining them; a short parenthetical definition at first use would improve readability.
  2. [Simulation section] Simulation figures comparing qubit/query cost versus trace distance would benefit from explicit captions stating the Markov chain family, the cooling schedule, and the numerical values chosen for the supplied overlap and gap lower bounds.
  3. [Section 6 (Gibbs application)] A brief remark on how the supplied lower bounds on overlaps and phase gaps might be obtained or bounded in the Gibbs-state application would help readers assess practicality, even if only as a high-level discussion.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading, positive recommendation, and constructive suggestions. We address each major comment below and will revise the manuscript accordingly to improve clarity and completeness.

read point-by-point responses

  1. Referee: [Section 3 (GQSP projector and selective phase compiler)] The one-ancilla claim and the sqrt-overlap improvement both rest on the GQSP-based selective phase compiler inside FPAA. The manuscript should supply an explicit resource count (qubit and gate) for this compiler, including how the projector is realized without additional ancillae beyond the stated single qubit (see the construction around the qubitized Szegedy walk).

    Authors: We agree that an explicit resource count would strengthen the presentation of the one-ancilla construction. In the revised manuscript we will add a dedicated subsection in Section 3 that tabulates the qubit and gate counts for the GQSP-based selective phase compiler. The new material will detail the circuit decomposition of the projector onto the 1-eigenspace of the qubitized Szegedy walk, confirming that the construction uses precisely one ancilla qubit and no additional working-register ancillae. revision: yes

  2. Referee: [Section 4 (complexity analysis)] The final query complexity is stated to be O(1/sqrt(delta_min * gamma_min) * polylog(1/epsilon)). The error-propagation analysis that converts the supplied lower bounds and the FPAA iteration count into this scaling (including the precise polylog factors) should be written out with explicit constants or big-O derivations rather than summarized.

    Authors: We accept that the current summary of the error-propagation analysis in Section 4 is insufficiently detailed. In the revision we will expand Section 4 with a self-contained derivation that traces the supplied lower bounds on overlaps and phase gaps through the FPAA iteration count, the error accumulation at each step, and the final conversion to the stated query complexity, including explicit polylogarithmic factors and the underlying big-O derivations. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation supplies an end-to-end QSAMPLE algorithm whose query complexity and ancilla count are stated explicitly conditional on externally supplied lower bounds for minimum overlap and minimum phase gap; these bounds are modeled as oracles/inputs rather than outputs of the procedure. The claimed improvements (one ancilla via GQSP projector inside FPAA, sqrt-overlap scaling) follow directly from the construction once those inputs are granted, building on the external prior framework of Wocjan and Abeyesinghe. No load-bearing step reduces by definition, by fitted-parameter renaming, or by self-citation chain to the target result itself.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The framework rests on standard quantum computing oracles and the provision of numerical lower bounds on overlaps and gaps; no new physical entities are introduced.

axioms (2)
  • standard math Standard quantum circuit model with oracle access to the Markov chain transition operator and its controlled version.
    Invoked throughout the description of the algorithm and query complexity.
  • domain assumption Reversibility of the Markov chains under consideration.
    Required for the Szegedy walk construction and the existence of a stationary distribution that can be encoded coherently.

pith-pipeline@v0.9.0 · 5842 in / 1450 out tokens · 18770 ms · 2026-05-25T04:48:15.882087+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages · 3 internal anchors

  1. [1]

    Quantum amplitude amplification and estimation,

    G. Brassard, P. Høyer, M. Mosca, and A. Tapp, “Quantum amplitude amplification and estimation,” inQuantum Computation and Information, AMS, 2002, pp. 53–74. doi: 10.1090/conm/305/05215

    work page doi:10.1090/conm/305/05215 2002

  2. [2]

    Quantum speedup of Monte Carlo methods,

    A. Montanaro, “Quantum speedup of Monte Carlo methods,”Proc. Royal Society A: Math., Phys., Eng. Sci., vol. 471, no. 2181, p. 20150301, Sep

    work page

  3. [3]

    doi: 10.1098/rspa.2015.0301

    work page doi:10.1098/rspa.2015.0301 2015

  4. [4]

    Near-optimal quantum algorithms for multivariate mean estimation,

    A. Cornelissen, Y . Hamoudi, and S. Jerbi, “Near-optimal quantum algorithms for multivariate mean estimation,” inProc. 54th Annu. ACM SIGACT Symp. Theory of Computing (STOC ’22), ACM, Jun. 2022, pp. 33–43. doi: 10.1145/3519935.3520045

    work page doi:10.1145/3519935.3520045 2022

  5. [5]

    Manca, S

    P. Wocjan and A. Abeyesinghe, “Speed-up via quantum sampling,”Phys- ical Review A, vol. 78, no. 4, p. 042336, Oct. 2008. doi: 10.1103/Phys- RevA.78.042336

    work page doi:10.1103/phys- 2008

  6. [6]

    Quantum Simulations of Classical Annealing Processes

    R. D. Somma, S. Boixo, H. Barnum, and E. Knill, “Quantum simu- lations of classical annealing processes,”Physical Review Letters, vol. 101, no. 13, p. 130504, 2008. doi: 10.1103/PhysRevLett.101.130504. arXiv:0804.1571

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.101.130504 2008

  7. [7]

    Quantum speed-up of Markov chain based algorithms,

    M. Szegedy, “Quantum speed-up of Markov chain based algorithms,” in Proc. 45th Annu. IEEE Symp. Foundations of Computer Science (FOCS), 2004, pp. 32–41. doi: 10.1109/FOCS.2004.53

    work page doi:10.1109/focs.2004.53 2004

  8. [8]

    Search via quantum walk,

    F. Magniez, A. Nayak, J. Roland, and M. Santha, “Search via quantum walk,”SIAM Journal on Computing, vol. 40, no. 1, pp. 142–164, Jan

    work page

  9. [9]

    doi: 10.1137/090745854

    work page doi:10.1137/090745854

  10. [10]

    Adaptive simulated annealing: A near-optimal connection between sampling and counting,

    D. ˇStefankoviˇc, S. Vempala, and E. Vigoda, “Adaptive simulated annealing: A near-optimal connection between sampling and counting,”J. ACM, vol. 56, no. 3, art. 18, May 2009. doi: 10.1145/1516512.1516520

    work page doi:10.1145/1516512.1516520 2009

  11. [11]

    A sublinear-time quantum algorithm for approximating partition functions,

    A. Cornelissen and Y . Hamoudi, “A sublinear-time quantum algorithm for approximating partition functions,” arXiv:2207.08643, 2023. doi: 10.1137/1.9781611977554.ch46

    work page doi:10.1137/1.9781611977554.ch46 2023

  12. [12]

    Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions,

    S. Arunachalam, V . Havlicek, G. Nannicini, K. Temme, and P. Wocjan, “Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions,”Quantum, vol. 6, p. 789, Sep. 2022. doi: 10.22331/q-2022- 09-01-789

    work page doi:10.22331/q-2022- 2022

  13. [13]

    Quantum algorithm for approximating partition functions,

    P. Wocjan, C.-F. Chiang, D. Nagaj, and A. Abeyesinghe, “Quantum algorithm for approximating partition functions,”Physical Review A, vol. 80, no. 2, p. 022340, Aug. 2009. doi: 10.1103/PhysRevA.80.022340

    work page doi:10.1103/physreva.80.022340 2009

  14. [14]

    Adaptive quantum simulated annealing for Bayesian inference and estimating partition functions,

    A. W. Harrow and A. Y . Wei, “Adaptive quantum simulated annealing for Bayesian inference and estimating partition functions,” inProc. 14th Annu. ACM-SIAM Symp. Discrete Algorithms, SIAM, 2020, pp. 193–212. doi: 10.1137/1.9781611975994.12

    work page doi:10.1137/1.9781611975994.12 2020

  15. [15]

    A fast quantum mechanical algorithm for database search

    L. K. Grover, “A fast quantum mechanical algorithm for database search,” arXiv:quant-ph/9605043, 1996

    work page internal anchor Pith review Pith/arXiv arXiv 1996

  16. [16]

    Fixed-point quantum search with an optimal number of queries,

    T. J. Yoder, G. H. Low, and I. L. Chuang, “Fixed-point quantum search with an optimal number of queries,”Physical Review Letters, vol. 113, no. 21, p. 210501, Nov. 2014. doi: 10.1103/PhysRevLett.113.210501

    work page doi:10.1103/physrevlett.113.210501 2014

  17. [17]

    Generalized quantum signal processing,

    D. Motlagh and N. Wiebe, “Generalized quantum signal processing,” PRX Quantum, vol. 5, no. 2, p. 020368, 2024. doi: 10.1103/PRXQuan- tum.5.020368

    work page doi:10.1103/prxquan- 2024

  18. [18]

    A simple algorithm to reflect through eigenspaces of unitaries,

    B. Claudon, “A simple algorithm to reflect through eigenspaces of unitaries,” arXiv:2412.09320, 2025

    work page arXiv 2025

  19. [19]

    Quan- tum circuits for the Metropolis-Hastings algorithm,

    B. Claudon, P. Rodenas-Ruiz, J.-P. Piquemal, and P. Monmarch ´e, “Quan- tum circuits for the Metropolis-Hastings algorithm,” arXiv:2506.11576, 2025

    work page arXiv 2025

  20. [20]

    Quantum speedup for nonreversible Markov chains,

    B. Claudon, J.-P. Piquemal, and P. Monmarch ´e, “Quantum speedup for nonreversible Markov chains,”Nature Communications, vol. 16, no. 1, Nov. 2025. doi: 10.1038/s41467-025-65761-5

    work page doi:10.1038/s41467-025-65761-5 2025

  21. [21]

    Adiabatic quantum state generation and statistical zero knowledge,

    D. Aharonov and A. Ta-Shma, “Adiabatic quantum state generation and statistical zero knowledge,” inProc. 35th Annu. ACM Symp. Theory of Computing (STOC ’03), ACM, 2003, pp. 20–29

    work page 2003

  22. [22]

    Quantum Lower Bound for the Collision Problem

    S. Aaronson, “Quantum lower bound for the collision problem,” arXiv:quant-ph/0111102, 2001

    work page internal anchor Pith review Pith/arXiv arXiv 2001