Ancilla-Efficient QSAMPLE Preparation for Reversible Markov Chains

• URL: http://arxiv.org/abs/2605.23442v1
• Date: Fri, 22 May 2026 09:55:28 GMT
• Title: Ancilla-Efficient QSAMPLE Preparation for Reversible Markov Chains
• Abstract summary: We present a new end-to-end framework requiring only one ancilla qubit in the working register.<n>The key technical ingredient is a selective phase compiler circuit using one ancilla qubit.<n>As a direct application, we apply the quantum algorithm to prepare a Gibbs QSAMPLE and obtain a rigorous complexity analysis.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Deterministic Quantum Phase Estimation with Linear Circuit Complexity in a Photonic System [4.969716969054012]
  Quantum algorithms solve certain computational problems faster than the best known classical algorithms.<n>We introduce a QPE algorithm that successfully reduces the circuit complexity from $mathcalO(n2)$ to $mathcalO(n)$ for a special class of unitary operators.
  arXiv  Detail & Related papers  (2026-07-15T03:02:14Z)
• Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization [0.7009487789080343]
  We investigate ancilla-free linear combination of unitaries (LCU) as a framework for approximating complex quantum circuits.<n>We show that Fourier-based LCU constructions efficiently decompose broad classes of diagonal and non-diagonal unitaries.
  arXiv  Detail & Related papers  (2026-05-18T18:05:08Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
  arXiv  Detail & Related papers  (2026-03-08T15:15:52Z)
• Sample- and Hardware-Efficient Fidelity Estimation by Stripping Phase-Dominated Magic [0.2796197251957245]
  This work proposes a sample- and gate-efficient fidelity estimation algorithm that is affordable within feasible quantum devices.<n>We show that the fidelity estimation with pure states close to the structure of phase states, for which sample-efficient DFE is limited by their strong entanglement and magic, can be done by using $mathcalO(mathrmpoly(n))$ sampling copies, with a single $n$-qubit fan-out gate.
  arXiv  Detail & Related papers  (2026-02-10T12:13:25Z)
• Continual Quantum Architecture Search with Tensor-Train Encoding: Theory and Applications to Signal Processing [68.35481158940401]
  CL-QAS is a continual quantum architecture search framework.<n>It mitigates challenges of costly encoding amplitude and forgetting in variational quantum circuits.<n>It achieves controllable robustness expressivity, sample-efficient generalization, and smooth convergence without barren plateaus.
  arXiv  Detail & Related papers  (2026-01-10T02:36:03Z)
• Tradeoffs between quantum and classical resources in linear combination of unitaries [0.07388859384645262]
  The linear combination of unitaries (LCU) algorithm is a building block of many quantum algorithms.<n>We propose a quantum algorithm that manages the tradeoff between sampling cost and the circuit size.
  arXiv  Detail & Related papers  (2025-12-06T03:10:22Z)
• Neural Guided Sampling for Quantum Circuit Optimization [26.90377134346014]
  Translating a quantum circuit on a specific hardware topology with a reduced set of available gates, also known as transpilation, comes with a substantial increase in the length of the equivalent circuit.<n>One method to address efficient transpilation is based on approaches known from optimization, e.g. by using random sampling and token replacement strategies.<n>Here, we propose in this work 2D neural guided sampling. Thus, given a 2D representation of a quantum circuit, a neural network predicts groups of gates in the quantum circuit, which are likely reducible.
  arXiv  Detail & Related papers  (2025-10-14T12:09:05Z)
• Randomized Quantum Singular Value Transformation [18.660349597156266]
  We introduce the first randomized algorithms for Quantum Singular Value Transformation (QSVT)<n>Standard implementations of QSVT rely on block encodings of the Hamiltonian, requiring a logarithmic number of ancilla qubits, intricate multi-qubit control, and circuit depth scaling linearly with the number of Hamiltonian terms.<n>Our algorithms use only a single ancilla qubit and entirely avoid block encodings.
  arXiv  Detail & Related papers  (2025-10-08T10:14:15Z)
• Accelerating Transpilation in Quantum Machine Learning with Haiqu's Rivet-transpiler [45.88028371034407]
  We develop the Rivet transpiler, which accelerates transpilation by reusing previously transpiled circuits.<n>We demonstrate up to 600% improvement in transpilation time for quantum layerwise learning.
  arXiv  Detail & Related papers  (2025-08-29T06:00:29Z)
• Modular Quantum Amplitude Estimation: A Scalable and Adaptive Framework [0.0]
  We introduce the Adaptive Windowed Quantum Amplitude Estimation (AWQAE) framework.<n>It is a modular, scalable and adaptive approach that decouples estimation precision from the number of physical qubits required in a single circuit.<n>AWQAE offers a powerful and flexible solution for performing high-precision QAE on resource-constrained quantum hardware.
  arXiv  Detail & Related papers  (2025-08-07T19:19:11Z)
• Variational preparation of entangled states in a system of transmon qubits [29.259008600842517]
  We use a minimally calibrated two-qubit i-Swap-like gate to prepare Bell states and GHZ states experimentally in systems of two and three transmon qubits.<n>Our proposed methodology employs variational quantum algorithms (VQAs) to create the target quantum state through imperfect multiqubit operations.
  arXiv  Detail & Related papers  (2025-04-02T14:09:26Z)
• Enhanced Quantum Circuit Cutting Framework for Sampling Overhead Reduction [25.01488143369413]
  ShotQC is an enhanced circuit cutting framework with effective sampling overhead reduction.<n>It achieves significant reductions in sampling overhead without increasing classical postprocessing complexity.
  arXiv  Detail & Related papers  (2024-12-23T16:34:57Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.