arxiv: 2604.24973 · v1 · submitted 2026-04-27 · 🪐 quant-ph

Recognition: unknown

Approximate Sparse State Preparation with the Grover-Rudolph Algorithm

Debora Ramacciotti , Martin Steinbach , Bence Temesi , Andreea-Iulia Lefterovici , Antonio F. Rotundo

Authors on Pith no claims yet

Pith reviewed 2026-05-08 03:47 UTC · model grok-4.3

classification 🪐 quant-ph

keywords sparse quantum state preparationGrover-Rudolph algorithmgate mergingapproximate preparationCNOT reductionquantum circuit optimizationstate fidelity estimation

0 comments

The pith

The Grover-Rudolph algorithm for sparse state preparation can be improved by merging rotations with virtual zero-angle gates and approximately merging similar angles to reduce CNOTs with controllable error.

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

This paper seeks to make sparse quantum state preparation more efficient by refining the Grover-Rudolph algorithm. The authors extend gate merging to include virtual zero-angle gates on unreachable branches of the preparation tree, which cuts down on CNOT gates and control qubits. They also propose an approximate merging approach for rotations with similar angles, accepting a small error that can be estimated classically to decide when to merge. These changes matter because sparse state preparation is a key step in many quantum algorithms, and lowering resource requirements could help implement them on current quantum hardware.

Core claim

By allowing rotations to merge with virtual zero-angle gates on unreachable branches and by merging rotations with similar but not identical angles, the number of CNOTs and control qubits is reduced while a classically computable estimate of the overlap with the target state guides the decisions and bounds the error.

What carries the argument

The preparation tree from the Grover-Rudolph algorithm, extended with a gate-merging procedure that incorporates virtual zero-angle gates and approximate merging of similar rotations.

If this is right

Exact preparation requires fewer CNOTs and control qubits when virtual merges are allowed.
Approximate preparation trades a small error for further resource savings.
The overlap estimate is computable on a classical computer before applying the circuit.
The method applies directly to states with few nonzero entries.
Error remains controllable by choosing which merges to perform based on the estimate.

Where Pith is reading between the lines

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

Such reductions could enable larger sparse states to be prepared on near-term quantum devices.
Similar merging ideas might apply to other state preparation or circuit optimization techniques.
Testing the estimate's accuracy on various sparse data sets would be a natural next step.

Load-bearing premise

That the classically computed overlap estimate accurately bounds or predicts the true overlap achieved by the quantum circuit after the merges have been performed.

What would settle it

Running the quantum circuit for a chosen sparse state, performing the merges, and comparing the measured fidelity or overlap to the classical estimate to see if they match within the predicted bounds.

Figures

Figures reproduced from arXiv: 2604.24973 by Andreea-Iulia Lefterovici, Antonio F. Rotundo, Bence Temesi, Debora Ramacciotti, Martin Steinbach.

**Figure 1.** Figure 1: Circuit diagram of a uniformly controlled y-rotation on view at source ↗

**Figure 2.** Figure 2: Preparation tree for the state |ψ⟩ = a |001⟩+b |011⟩+ c |100⟩. The highlighted leaves are the nonzero basis states of the target state, while faded nodes indicate zero-amplitude branches. The non-faded nodes correspond to the nonzero prefix sets Sk. The coarse-grained state |ψ (2)⟩, for instance, is given by a |00⟩ + b |01⟩ + c |10⟩. |ψ (k−1)⟩ by appending an ancilla qubit |0⟩ and performing a rotation of … view at source ↗

**Figure 3.** Figure 3: Example of optimization procedure. Here, view at source ↗

**Figure 4.** Figure 4: CNOT reduction due to the exact merges. We plot view at source ↗

**Figure 6.** Figure 6: Performance assessment of the overlap estimation. The view at source ↗

**Figure 8.** Figure 8: Comparison between the exact and the approximate view at source ↗

read the original abstract

Sparse quantum state preparation is a common subroutine in quantum algorithms, where classical data with few nonzero entries must be loaded into a quantum state. In this work, we consider the Grover-Rudolph algorithm, which has recently been shown to efficiently prepare sparse states, and we propose two improvements. First, we extend an existing gate-merging procedure by allowing rotations to merge with virtual zero-angle gates on unreachable branches of the preparation tree, reducing the number of CNOTs and control qubits. Second, we introduce an approximate variant in which rotations with similar but not identical angles are merged at the cost of a small, controllable error in the prepared state. We derive a classically computable estimate of the resulting overlap with the target state, which is used to guide the merging decisions.

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.

Desk Editor's Note private letter to a colleague

The paper adds two practical gate-saving tweaks to Grover-Rudolph sparse prep via virtual zero merges and approximate angle merges with a classical overlap estimate, but the estimate's handling of merge dependencies needs verification.

read the letter

The main things to know are that the authors extend gate merging in Grover-Rudolph to include virtual zero-angle rotations on unreachable branches, which trims CNOTs and controls, and they add an approximate merge rule for similar angles that uses a classically computable overlap estimate to keep the error small and controllable. Both changes target real circuit costs in sparse state preparation, a subroutine that shows up in linear systems and optimization algorithms. The virtual-zero extension is new relative to the cited prior work and looks like a direct, low-risk improvement. The approximate variant is also new and gives a concrete way to trade a bit of fidelity for fewer gates while staying deterministic on the classical side. That combination is useful for near-term hardware where every CNOT counts. The paper does well by staying focused on implementable reductions rather than asymptotic claims. The soft spot is the overlap estimate. It is presented as independently computable from the amplitudes and used to guide merges, but the derivation must show that the bound survives when one merge alters the angles or controls seen by later steps. If the math treats merges as isolated perturbations whose errors multiply independently, shared qubits or depth effects could loosen the guarantee. The abstract does not detail how those interactions are handled, so the claim that the error stays controllable rests on whether the full proof accounts for tree-wide dependence. Numerical checks on varied sparse vectors would help here. This is for people who build or optimize quantum circuits that load sparse data. A reader working on concrete implementations will get usable gate-count reductions even if the error analysis needs tightening. It deserves peer review because the ideas are grounded in an existing algorithm and the estimate offers a practical handle on approximation, provided the dependencies are clarified.

Referee Report

2 major / 2 minor

Summary. The manuscript extends the Grover-Rudolph algorithm for preparing sparse quantum states by (i) allowing rotations to merge with virtual zero-angle gates on unreachable branches of the preparation tree, thereby reducing CNOT count and control-qubit overhead, and (ii) introducing an approximate merging rule that combines rotations whose angles differ by a small amount, incurring a controllable error. A classically computable estimate of the overlap between the prepared state and the target state is derived and used to decide which merges to perform.

Significance. If the overlap estimate is shown to be a rigorous lower bound that remains valid under sequential merges, the work would provide a practical route to shallower circuits for sparse state preparation, a subroutine appearing in many quantum algorithms. The classical computability of the estimate is a concrete strength that could enable automated circuit optimization without quantum simulation.

major comments (2)

[§4.2] §4.2, the derivation of the overlap estimate: the argument treats each merge as an isolated perturbation whose fidelity factor multiplies independently, but does not address correlations that arise when one merge changes the angle distribution seen by later merges in the same subtree. A concrete counter-example or inductive argument showing that the product of per-merge factors still lower-bounds the final overlap is required.
[§5.1] §5.1, numerical validation: the reported fidelity curves compare the approximate circuit only against the exact Grover-Rudolph circuit on randomly chosen sparse vectors; no stress test is provided for the worst-case angle configurations that would maximize the discrepancy between the classical estimate and the true quantum overlap after all merges have been performed.

minor comments (2)

Notation: the symbol used for the per-merge fidelity factor is introduced without an explicit definition in the main text; a short displayed equation would remove ambiguity.
Figure 3: the legend does not indicate which curves correspond to the exact versus approximate merging procedures; adding this information would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. The points raised regarding the rigor of the overlap estimate and the scope of numerical validation are well taken. We respond to each major comment below and have revised the manuscript to address them.

read point-by-point responses

Referee: [§4.2] §4.2, the derivation of the overlap estimate: the argument treats each merge as an isolated perturbation whose fidelity factor multiplies independently, but does not address correlations that arise when one merge changes the angle distribution seen by later merges in the same subtree. A concrete counter-example or inductive argument showing that the product of per-merge factors still lower-bounds the final overlap is required.

Authors: We appreciate the referee highlighting this potential gap in the sequential application of merges. The original derivation in §4.2 considered the effect of each merge on the local subtree fidelity. To address correlations explicitly, we have added an inductive argument in the revised §4.2. The induction proceeds over the depth of the preparation tree: the base case at the leaves is trivial (exact overlap of 1). For the inductive step, we show that if the estimate lower-bounds the overlap up to a given level, then performing a merge at that level (which may alter angles for descendant merges) preserves the lower-bound property for the updated distribution. This follows from the monotonicity of the cosine-based fidelity factor under small angle perturbations and the fact that the Grover-Rudolph tree structure ensures that angle updates remain within the same subtree. A small worked example with two sequential merges is included to illustrate that the product of factors remains a valid lower bound. We believe this resolves the concern without altering the classical computability of the estimate. revision: yes
Referee: [§5.1] §5.1, numerical validation: the reported fidelity curves compare the approximate circuit only against the exact Grover-Rudolph circuit on randomly chosen sparse vectors; no stress test is provided for the worst-case angle configurations that would maximize the discrepancy between the classical estimate and the true quantum overlap after all merges have been performed.

Authors: We agree that random sampling alone does not fully stress-test the estimate. In the revised §5.1 we have added a new set of experiments using adversarially chosen angle configurations. These include (i) alternating large and near-zero angles within the same subtree to maximize potential error propagation, and (ii) configurations where multiple merges occur at the same depth with angle differences tuned to the boundary of the merging threshold. For each case we compute both the classical estimate and the exact quantum overlap (via direct simulation for small n). The results confirm that the estimate remains a strict lower bound, with the gap between estimate and true overlap staying within the analytically predicted range. We have also included a brief description of how such worst-case instances can be generated classically, which may be useful for automated verification. revision: yes

Circularity Check

0 steps flagged

No circularity detected in derivation chain

full rationale

The paper presents the overlap estimate as a direct classical computation from the given target amplitudes, used to guide (but not defined by) the merging decisions. No equations reduce the estimate to a fitted parameter, self-referential definition, or quantity forced by the same merges it evaluates. The gate-merging extensions and approximate variant are described as procedural improvements whose error bound is computed independently from the input data, with no load-bearing self-citations, imported uniqueness theorems, or ansatzes that collapse the central claim to its own inputs. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard quantum circuit model and the correctness of the original Grover-Rudolph tree construction; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)

standard math Quantum circuits are composed of unitary gates acting on qubits with standard CNOT and single-qubit rotation primitives.
Implicit in any gate-counting claim for quantum state preparation.
domain assumption The target state is exactly sparse with known nonzero amplitudes.
Required for the Grover-Rudolph tree to be well-defined.

pith-pipeline@v0.9.0 · 5441 in / 1404 out tokens · 33370 ms · 2026-05-08T03:47:47.873226+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

26 extracted references · 7 canonical work pages

[1]

Approximation by quantum circuits.arXiv preprint quant-ph/9508006, 1995

Emanuel Knill. Approximation by quantum circuits.arXiv preprint quant-ph/9508006, 1995

work page arXiv 1995
[2]

Simulating quantum systems on a quan- tum computer.Proceedings of the Royal Society of London

Christof Zalka. Simulating quantum systems on a quan- tum computer.Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454(1969):313–322, 1998

1969
[3]

Quantum networks for generating arbitrary quantum states

Phillip Kaye and Michele Mosca. Quantum networks for generating arbitrary quantum states. InInternational Conference on Quantum Information, page PB28. Optica Publishing Group, 2001

2001
[4]

Creating superpositions that correspond to efficiently integrable probability distributions

Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv preprint quant-ph/0208112, 2002

work page Pith review arXiv 2002
[5]

Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023

Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023

2023
[6]

An efficient algorithm for sparse quantum state preparation

Niels Gleinig and Torsten Hoefler. An efficient algorithm for sparse quantum state preparation. In2021 58th ACM/IEEE Design Automation Conference (DAC), pages 433–438. IEEE, 2021

2021
[7]

Quantum circuits for sparse isometries.Quantum, 5:412, 2021

Emanuel Malvetti, Raban Iten, and Roger Colbeck. Quantum circuits for sparse isometries.Quantum, 5:412, 2021

2021
[8]

Double sparse quantum state preparation.Quantum Information Processing, 21(6):204, 2022

Tiago ML de Veras, Leon D da Silva, and Adenilton J da Silva. Double sparse quantum state preparation.Quantum Information Processing, 21(6):204, 2022

2022
[9]

Efficient deterministic preparation of quantum states using de- cision diagrams.Physical Review A, 106(2):022617, 2022

Fereshte Mozafari, Giovanni De Micheli, and Yuxiang Yang. Efficient deterministic preparation of quantum states using de- cision diagrams.Physical Review A, 106(2):022617, 2022

2022
[10]

Quantum state preparation with optimal circuit depth: Implementations and applications.Physical Review Letters, 129(23):230504, 2022

Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. Quantum state preparation with optimal circuit depth: Implementations and applications.Physical Review Letters, 129(23):230504, 2022

2022
[11]

Simple quantum algorithm to efficiently prepare sparse states.Physical Review A, 110(3):032609, 2024

Debora Ramacciotti, Andreea I Lefterovici, and Antonio F Rotundo. Simple quantum algorithm to efficiently prepare sparse states.Physical Review A, 110(3):032609, 2024

2024
[12]

Toward optimal circuit size for sparse quantum state preparation.Phys

Rui Mao, Guojing Tian, and Xiaoming Sun. Toward optimal circuit size for sparse quantum state preparation.Phys. Rev. A, 110:032439, Sep 2024

2024
[13]

Sparse quantum state preparation with improved toffoli cost.arXiv preprint arXiv:2601.09388, 2026

Felix Rupprecht and Sabine Wölk. Sparse quantum state preparation with improved toffoli cost.arXiv preprint arXiv:2601.09388, 2026

work page arXiv 2026
[14]

Nearly optimal circuit size for sparse quantum state preparation.arXiv preprint arXiv:2406.16142, 2024

Lvzhou Li and Jingquan Luo. Nearly optimal circuit size for sparse quantum state preparation.arXiv preprint arXiv:2406.16142, 2024

work page arXiv 2024
[15]

Beyond nisq: The megaquop machine.ACM Transactions on Quantum Computing, 6(3):1–7, 2025

John Preskill. Beyond nisq: The megaquop machine.ACM Transactions on Quantum Computing, 6(3):1–7, 2025

2025
[16]

Mind the gaps: The fraught road to quantum advantage

Jens Eisert and John Preskill. Mind the gaps: The fraught road to quantum advantage.arXiv preprint arXiv:2510.19928, 2025

work page arXiv 2025
[17]

Quantum algorithms for approximate function loading

Gabriel Marin-Sanchez, Javier Gonzalez-Conde, and Mikel Sanz. Quantum algorithms for approximate function loading. Physical Review Research, 5(3):033114, 2023

2023
[18]

Markov, and Robert Wille

Alwin Zulehner, Stefan Hillmich, Igor L. Markov, and Robert Wille. Approximation of quantum states using decision dia- grams. In2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC), page 121–126. IEEE, January 2020

2020
[19]

Encoding proteins as quantum states with approximate quantum state preparation by iterated sparse state preparation

Rod Rofougaran, Ralph Wang, Akshay Ajagekar, and Fengqi You. Encoding proteins as quantum states with approximate quantum state preparation by iterated sparse state preparation. Quantum Science and Technology, 10(2):025029, feb 2025

2025
[20]

Exploring the optimality of approximate state preparation quantum circuits with a genetic algorithm.Physics Letters A, 475:128860, 2023

Tom Rindell, Berat Yenilen, Niklas Halonen, Arttu Pönni, Ilkka Tittonen, and Matti Raasakka. Exploring the optimality of approximate state preparation quantum circuits with a genetic algorithm.Physics Letters A, 475:128860, 2023

2023
[21]

Efficient quantum circuits for non-unitary and unitary diagonal operators with space-time-accuracy trade-offs

Julien Zylberman, Ugo Nzongani, Andrea Simonetto, and Fab- rice Debbasch. Efficient quantum circuits for non-unitary and unitary diagonal operators with space-time-accuracy trade-offs. ACM Transactions on Quantum Computing, 6(2):1–43, 2025

2025
[22]

Araujo, Carsten Blank, Ismael C

Israel F. Araujo, Carsten Blank, Ismael C. S. Araújo, and Adenilton J. da Silva. Low-rank quantum state preparation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 43(1):161–170, 2024

2024
[23]

Möttönen, J

M. Möttönen, J. J. Vartiainen, V . Bergholm, and M. M. Salomaa. Transformation of quantum states using uniformly controlled rotations.Quantum Information and Computation, 5(6):467– 473, September 2005

2005
[24]

Shende, S.S

V .V . Shende, S.S. Bullock, and I.L. Markov. Synthesis of quantum-logic circuits.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(6):1000–1010, June 2006

2006
[25]

Decomposition of multi- controlled special unitary single-qubit gates.arXiv preprint arXiv:2302.06377, 2023

Rafaella Vale, Thiago Melo D Azevedo, Ismael Araújo, Israel F Araujo, and Adenilton J da Silva. Decomposition of multi- controlled special unitary single-qubit gates.arXiv preprint arXiv:2302.06377, 2023

work page arXiv 2023
[26]

Multi-controlled quantum gates in linear nearest neighbor.arXiv preprint arXiv:2506.00695, 2025

Ben Zindorf and Sougato Bose. Multi-controlled quantum gates in linear nearest neighbor.arXiv preprint arXiv:2506.00695, 2025

work page arXiv 2025