Sparse quantum state preparation with improved Toffoli cost

• URL: http://arxiv.org/abs/2601.09388v1
• Date: Wed, 14 Jan 2026 11:28:27 GMT
• Title: Sparse quantum state preparation with improved Toffoli cost
• Authors: Felix Rupprecht, Sabine Wölk,
• Abstract summary: Preparation of quantum states is one of the most fundamental tasks in quantum computing.<n>We present an approach that prepares sparse quantum states on $n$ qubits.<n>The speed-up is achieved by designing an efficient algorithm for finding and implementing the isometry.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The preparation of quantum states is one of the most fundamental tasks in quantum computing, and a key primitive in many quantum algorithms. Of particular interest to areas such as quantum simulation and linear-system solvers are sparse quantum states, which contain only a small number $s$ of non-zero computational basis states compared to a generic state. In this work, we present an approach that prepares $s$-sparse states on $n$ qubits, reducing the number of Toffoli gates required compared to prior art. We work in the established framework of first preparing a dense state on a $\lceil{\log(s)}\rceil$-qubit sub-register, and then mapping this state to the target state via an isometry, with the latter step dominating the cost of the full algorithm. The speed-up is achieved by designing an efficient algorithm for finding and implementing the isometry. The worst-case Toffoli cost of our isometry circuit, which may be viewed as a batched version of an approach by Malvetti et al., is essentially $2s$ for sufficiently large values of $n$, yielding roughly a $\log(s)/2$ improvement factor over the state-of-the-art. In numerical benchmarks on randomly chosen states, the cost is closer to $s$. With the improved isometry circuit, we examine the dense-state preparation step and present ways to optimize the joint cost of both steps, particularly in the case of target states with purely real coefficients, by outsourcing some sub-tasks from the dense-state preparation to the isometry.

Related papers

• 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)
• Efficient circuits for leaf-separable state preparation [0.0]
  We present a state preparation algorithm that combines logarithmic-depth Dicke state circuits with Hamming weight encoders for efficiently preparing leaf-separable" quantum states.<n>We evaluate the performance of the algorithm by numerically simulating it on randomly generated target states with between 4 and 15 qubits.<n>These results contribute to scalable state preparation for quantum algorithms that require structured inputs such as Dicke or near-Dicke states.
  arXiv  Detail & Related papers  (2025-11-14T12:30:08Z)
• Efficient Quantum State Preparation with Bucket Brigade QRAM [47.72095699729477]
  Preparation of data in quantum states is a critical component in the design of quantum algorithms.<n>One of the main approaches to achieve efficient state preparation is through the use of Quantum Random Access Memory (QRAM)<n>We present a framework that integrates the physical model of the Bucket Brigade QRAM (BBQRAM) with the classical data structure of the Segment Tree to achieve efficient state preparation.
  arXiv  Detail & Related papers  (2025-10-17T18:50:07Z)
• Shallow quantum circuit for generating O(1)-entangled approximate state designs [6.161617062225404]
  We find a new ensemble of quantum states that serve as an $epsilon$-approximate state $t$-design while possessing extremely low entanglement, magic, and coherence.<n>These resources can reach their theoretical lower bounds, $Omega(log (t/epsilon))$, which are also proven in this work.<n>A class of quantum circuits proposed in our work offers reduced cost for classical simulation of random quantum states.
  arXiv  Detail & Related papers  (2025-07-23T18:56:19Z)
• Augmenting Simulated Noisy Quantum Data Collection by Orders of Magnitude Using Pre-Trajectory Sampling with Batched Execution [47.60253809426628]
  We present the Pre-Trajectory Sampling technique, increasing efficiency and utility of trajectory simulations by tailoring error types.<n>We generate massive datasets of one trillion and one million shots, respectively.
  arXiv  Detail & Related papers  (2025-04-22T22:36:18Z)
• Enhancing Quantum State Reconstruction with Structured Classical Shadows [22.432806329828782]
  We introduce a projected classical shadow (PCS) method with guaranteed performance for QST based on Haar-random projective measurements.<n>PCS extends the standard CS method by incorporating a projection step onto the target subspace.<n>For matrix product operator states, we demonstrate that the PCS method can recover the ground-truth state with $O(n2)$ total state copies.
  arXiv  Detail & Related papers  (2025-01-06T17:09:38Z)
• Reclaiming Residual Knowledge: A Novel Paradigm to Low-Bit Quantization [41.94295877935867]
  This paper explores a novel paradigm in low-bit (i.e. 4-bits or lower) quantization, by framing optimal quantization as an architecture search problem within convolutional neural networks (ConvNets) Our framework, dubbed textbfCoRa, searches for the optimal architectures of low-rank adapters. textbfCoRa achieves comparable performance against both state-of-the-art quantization-aware training and post-training quantization baselines.
  arXiv  Detail & Related papers  (2024-08-01T21:27:31Z)
• Efficient learning of quantum states prepared with few fermionic non-Gaussian gates [0.0]
  We present an efficient algorithm for learning states on $n$ fermion modes prepared by any number of Gaussian gates.<n>Our work sheds light on the structure of states prepared with few non-Gaussian gates and offers an improved upper bound on their circuit complexity.
  arXiv  Detail & Related papers  (2024-02-28T19:18:27Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Efficient Verification of Anticoncentrated Quantum States [0.38073142980733]
  I present a novel method for estimating the fidelity $F(mu,tau)$ between a preparable quantum state $mu$ and a classically specified target state $tau$. I also present a more sophisticated version of the method, which uses any efficiently preparable and well-characterized quantum state as an importance sampler.
  arXiv  Detail & Related papers  (2020-12-15T18:01:11Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.