Approximate Sparse State Preparation with the Grover-Rudolph Algorithm

• URL: http://arxiv.org/abs/2604.24973v1
• Date: Mon, 27 Apr 2026 20:15:04 GMT
• Title: Approximate Sparse State Preparation with the Grover-Rudolph Algorithm
• Abstract summary: We consider the Grover-Rudolph algorithm, which has recently been shown to efficiently prepare sparse states.<n>We extend an existing gate-merging procedure by allowing rotations to merge with virtual zero-angle gates on unreachable branches of the preparation tree.<n>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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Coherent Quantum Schrodinger Bridge: Two-Boundary Optimal Control for Quantum Algorithm Design [0.913755431537592]
  We formulate this observation as a coherent Quantum Schrdinger Bridge (QSB)<n>We apply this framework to unstructured search, periodicity finding, and matrix arithmetic.<n>The usual circuit components -- oracles, diffusion reflections, controlled phases, and signal-processing rotations -- emerge as Lie-algebraic syntheses of the optimal weak-value drift.
  arXiv  Detail & Related papers  (2026-07-12T03:30:50Z)
• Efficient Complex-Valued State Preparation on Bucket Brigade QRAM [47.72095699729477]
  Efficient quantum state preparation is a critical component in quantum algorithms that process large classical data.<n>We present two improvements within the same architecture-aware framework.
  arXiv  Detail & Related papers  (2026-04-28T13:43:29Z)
• Algebraic Reduction to Improve an Optimally Bounded Quantum State Preparation Algorithm [0.6875312133832078]
  Preparation of $n$-qubit quantum states is a cross-cutting subroutine for many quantum algorithms.<n>A simpler algebraic decomposition is proposed to separate the preparation of the real part of the desired state from the complex one.<n>The reduction in complexity is due to the use of a single operator $$ for each uniformly controlled gate, instead of the three in the original decomposition.
  arXiv  Detail & Related papers  (2026-02-06T09:40:09Z)
• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  We develop a variational approach that creates an equal superposition of quantum states that satisfy constraints in a QCBO.<n>The resulting equal superposition can be used as an initial state for quantum algorithms that solve QUBOs/QCBOs.
  arXiv  Detail & Related papers  (2025-08-04T16:44:53Z)
• Arbitrary state creation via controlled measurement [49.494595696663524]
  This algorithm creates an arbitrary $n$-qubit pure quantum superposition state with precision of $m$-decimals.<n>The algorithm uses one-qubit rotations, Hadamard transformations and C-NOT operations with multi-qubit controls.
  arXiv  Detail & Related papers  (2025-04-13T07:23:50Z)
• Remarks on controlled measurement and quantum algorithm for calculating Hermitian conjugate [46.13392585104221]
  We present two new aspects for the recently proposed algorithms for matrix manipulating.<n>First aspect is the controlled measurement which allows to avoid the problem of small access probability to the required ancilla state.<n>Second aspect is the algorithm for calculating the Hermitian conjugate of an arbitrary matrix.
  arXiv  Detail & Related papers  (2025-01-27T13:11:47Z)
• Quantum State Preparation Circuit Optimization Exploiting Don't Cares [6.158168913938158]
  Quantum state preparation initializes the quantum registers and is essential for running quantum algorithms. Existing methods synthesize an initial circuit and leverage compilers to reduce the circuit's gate count. We introduce a peephole optimization algorithm that identifies such unitaries for replacement in the original circuit.
  arXiv  Detail & Related papers  (2024-09-02T18:40:42Z)
• A simple quantum algorithm to efficiently prepare sparse states [0.0]
  We show that the gate complexity is linear in the number of non-zero amplitudes in the state and quadratic in the number of qubits. This is competitive with the best known algorithms for sparse state preparation.
  arXiv  Detail & Related papers  (2023-10-30T07:05:15Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
  We present a quantum circuit compiler that prepares an algorithm-specific graph state from quantum circuits described in high level languages. The computation can then be implemented using a series of non-Pauli measurements on this graph state.
  arXiv  Detail & Related papers  (2022-09-15T14:52:31Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Quantum Search for Scaled Hash Function Preimages [1.3299507495084417]
  We present the implementation of Grover's algorithm in a quantum simulator to perform a quantum search for preimages of two scaled hash functions. We show that strategies that suggest a shortcut based on sampling the quantum register after a few steps of Grover's algorithm can only provide some marginal practical advantage in terms of error mitigation.
  arXiv  Detail & Related papers  (2020-09-01T18:00:02Z)
• Quantum state preparation with multiplicative amplitude transduction [0.0]
  Two variants of the algorithm with different emphases are introduced. One variant uses fewer qubits and no controlled gates, while the other variant potentially requires fewer gates overall. A general analysis is given to estimate the number of qubits necessary to achieve a desired precision in the amplitudes of the computational basis states.
  arXiv  Detail & Related papers  (2020-06-01T14:36:50Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

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.