Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.24973

Approximate Sparse State Preparation with the Grover-Rudolph Algorithm

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

quant-phSubmitted Apr 27, 2026• Announced Apr 29, 2026• 0 citations
arXivHTMLPDF

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

Simple quantum algorithm to efficiently prepare sparse states

Debora Ramacciotti, Andreea-Iulia Lefterovici, Antonio F. Rotundo

State preparation is a fundamental routine in quantum computation, for which many algorithms have been proposed. Among them, perhaps the simplest one is the Grover-Rudolph algorithm. In this paper we analyze the performance of this algorithm when the state to prepare is sparse. We show that the gate complexity is linear in the number of nonzero amplitudes in the state and quadratic in the number of qubits. We then introduce a simple modification of the algorithm, which makes the dependence on the number of qubits also linear. This is competitive with the best known algorithms for sparse state preparation.

Physical Review A•Sep 10, 2024•12 citations

A simple quantum algorithm to efficiently prepare sparse states

Debora Ramacciotti, Andreea-Iulia Lefterovici, Antonio F. Rotundo

State preparation is a fundamental routine in quantum computation, for which many algorithms have been proposed. Among them, perhaps the simplest one is the Grover-Rudolph algorithm. In this paper, we analyse the performance of this algorithm when the state to prepare is sparse. 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. We then introduce a simple modification of the algorithm, which makes the dependence on the number of qubits also linear. This is competitive with the best known algorithms for sparse state preparation

arXiv:2310.19309•Oct 30, 2023•0 citations

Sparse quantum state preparation with improved Toffoli cost

Felix Rupprecht, Sabine Wölk

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.

quant-pharXiv:2601.09388•Quantum•Jan 15, 2026•0 citations

Quantum algorithms for approximate function loading

Gabriel Marin-Sanchez, Javier Gonzalez-Conde, Mikel Sanz

Loading classical data into quantum computers represents an essential stage in many relevant quantum algorithms, especially in the field of quantum machine learning. Therefore, the inefficiency of this loading process means a major bottleneck for the application of these algorithms. Here, we introduce two approximate quantum-state preparation methods for the noisy intermediate-scale quantum era inspired by the Grover-Rudolph algorithm, which partially solve the problem of loading real functions. Indeed, by allowing for an infidelity $\ensuremath{\epsilon}$ and under certain smoothness conditions, we prove that the complexity of the implementation of the Grover-Rudolph algorithm without ancillary qubits, first introduced by M\"ott\"onen et al., results into $\mathcal{O}({2}^{{k}_{0}(\ensuremath{\epsilon})})$, with $n$ the number of qubits and ${k}_{0}(\ensuremath{\epsilon})$ asymptotically independent of $n$. This leads to a dramatic reduction in the number of required two-qubit gates. Aroused by this result, we also propose a variational algorithm capable of loading functions beyond the aforementioned smoothness conditions. Our variational Ansatz is explicitly tailored to the landscape of the function, leading to a quasioptimized number of hyperparameters. This allows us to achieve high fidelity in the loaded state with high speed convergence for the studied examples.

arXiv:2111.07933•Physical Review Research•Aug 18, 2023•43 citations

Circuit-based quantum random access memory for sparse quantum state preparation

Tiago M. L. Veras

In order to use a quantum device to assess a classical dataset D, we need to representthe set D in a quantum state. Applying a quantum algorithm, that is a quantum state preparation algorithm, to convert classical data into quantum data would be the common method. Loading classical data into a quantum device is required in many current applications. Efficiently preparing a quantum state to be used as the initial state of a quantum algorithm is an essential step in developing efficient quantum algorithms, since many algorithms need to reload the initial state several times during their execution. The cost to initialize a quantum state can compromise the algorithm efficiency if the process of quantum states preparation is not efficient. The topic of quantum states preparation in quantum computing has been the focus of much attention. In this scope, preparing sparse quantum states is a more specific problem that remains open since many quantum algorithms also require sparse initialization. This dissertation presents the results of an investigation on sparse quantum states preparation with the development of three algorithms, with highlight to the preparation of sparse quantum states, the main contributionof this dissertation. From a classical input dataset with M patterns formed by pairs composed of a complex number and a binary pattern with n bits, this algorithm can prepare a quantum state with n qubits and continuous amplitudes. The cost of its steps is O(nM), classical cost of o(MlogM+nM)and requires a lower CNOT number than the main quantum state preparation algorithms currently known. The preparation of a quantumstate with 2 non-zero amplitudes reveals the need of fewer CNOT gates in n>>1 relation to the main known state preparation algorithms, with even more favorable results with s higher and less 1S in the binary string.

•Sep 13, 2021•0 citations

Efficient sparse state preparation via quantum walks

Alvin Gonzales, Rebekah Herrman, Colin Campbell +4 more

Continuous-time quantum walks (CTQWs) on dynamic graphs, referred to as dynamic CTQWs, are a recently introduced universal model of computation that offers a new paradigm in which to envision quantum algorithms. In this work, we develop an algorithm that converts single-edge and self-loop dynamic CTQWs to the gate model of computation. We use this mapping to introduce an efficient sparse quantum state preparation framework based on dynamic CTQWs. Our approach utilizes combinatorics techniques such as minimal hitting sets, minimum spanning trees, and shortest Hamiltonian paths to reduce the number of controlled gates required to prepare sparse states. We show that our framework encompasses the current state of the art ancilla-free sparse state preparation method by reformulating this method as a CTQW. This CTQW-based framework offers an alternative to the uniformly controlled rotation method used by Qiskit by requiring fewer CX gates when the target state has a polynomial number of non-zero amplitudes.

arXiv:2405.20273•npj Quantum Information•Aug 21, 2025•2 citations
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.
State preparation is a fundamental routine in quantum computation, for which many algorithms have been proposed. Among them, perhaps the simplest one is the Grover-Rudolph algorithm. In this paper we analyze the performance of this algorithm when the state to prepare is sparse. We show that the gate complexity is linear in the number of nonzero amplitudes in the state and quadratic in the number of qubits. We then introduce a simple modification of the algorithm, which makes the dependence on the number of qubits also linear. This is competitive with the best known algorithms for sparse state preparation.
State preparation is a fundamental routine in quantum computation, for which many algorithms have been proposed. Among them, perhaps the simplest one is the Grover-Rudolph algorithm. In this paper, we analyse the performance of this algorithm when the state to prepare is sparse. 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. We then introduce a simple modification of the algorithm, which makes the dependence on the number of qubits also linear. This is competitive with the best known algorithms for sparse state preparation
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 sss of non-zero computational basis states compared to a generic state. In this work, we present an approach that prepares sss-sparse states on nnn 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 ⌈log⁡(s)⌉\lceil{\log(s)}\rceil⌈log(s)⌉-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 2s2s2s for sufficiently large values of nnn, yielding roughly a log⁡(s)/2\log(s)/2log(s)/2 improvement factor over the state-of-the-art. In numerical benchmarks on randomly chosen states, the cost is closer to sss. 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.
Loading classical data into quantum computers represents an essential stage in many relevant quantum algorithms, especially in the field of quantum machine learning. Therefore, the inefficiency of this loading process means a major bottleneck for the application of these algorithms. Here, we introduce two approximate quantum-state preparation methods for the noisy intermediate-scale quantum era inspired by the Grover-Rudolph algorithm, which partially solve the problem of loading real functions. Indeed, by allowing for an infidelity $\ensuremath{\epsilon}$ and under certain smoothness conditions, we prove that the complexity of the implementation of the Grover-Rudolph algorithm without ancillary qubits, first introduced by M\"ott\"onen et al., results into $\mathcal{O}({2}^{{k}_{0}(\ensuremath{\epsilon})})$, with nnn the number of qubits and ${k}_{0}(\ensuremath{\epsilon})$ asymptotically independent of nnn. This leads to a dramatic reduction in the number of required two-qubit gates. Aroused by this result, we also propose a variational algorithm capable of loading functions beyond the aforementioned smoothness conditions. Our variational Ansatz is explicitly tailored to the landscape of the function, leading to a quasioptimized number of hyperparameters. This allows us to achieve high fidelity in the loaded state with high speed convergence for the studied examples.
In order to use a quantum device to assess a classical dataset D, we need to representthe set D in a quantum state. Applying a quantum algorithm, that is a quantum state preparation algorithm, to convert classical data into quantum data would be the common method. Loading classical data into a quantum device is required in many current applications. Efficiently preparing a quantum state to be used as the initial state of a quantum algorithm is an essential step in developing efficient quantum algorithms, since many algorithms need to reload the initial state several times during their execution. The cost to initialize a quantum state can compromise the algorithm efficiency if the process of quantum states preparation is not efficient. The topic of quantum states preparation in quantum computing has been the focus of much attention. In this scope, preparing sparse quantum states is a more specific problem that remains open since many quantum algorithms also require sparse initialization. This dissertation presents the results of an investigation on sparse quantum states preparation with the development of three algorithms, with highlight to the preparation of sparse quantum states, the main contributionof this dissertation. From a classical input dataset with M patterns formed by pairs composed of a complex number and a binary pattern with n bits, this algorithm can prepare a quantum state with n qubits and continuous amplitudes. The cost of its steps is O(nM), classical cost of o(MlogM+nM)and requires a lower CNOT number than the main quantum state preparation algorithms currently known. The preparation of a quantumstate with 2 non-zero amplitudes reveals the need of fewer CNOT gates in n>>1 relation to the main known state preparation algorithms, with even more favorable results with s higher and less 1S in the binary string.
Continuous-time quantum walks (CTQWs) on dynamic graphs, referred to as dynamic CTQWs, are a recently introduced universal model of computation that offers a new paradigm in which to envision quantum algorithms. In this work, we develop an algorithm that converts single-edge and self-loop dynamic CTQWs to the gate model of computation. We use this mapping to introduce an efficient sparse quantum state preparation framework based on dynamic CTQWs. Our approach utilizes combinatorics techniques such as minimal hitting sets, minimum spanning trees, and shortest Hamiltonian paths to reduce the number of controlled gates required to prepare sparse states. We show that our framework encompasses the current state of the art ancilla-free sparse state preparation method by reformulating this method as a CTQW. This CTQW-based framework offers an alternative to the uniformly controlled rotation method used by Qiskit by requiring fewer CX gates when the target state has a polynomial number of non-zero amplitudes.