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

Entanglement as a complexity measure for quantum state preparation.

Israel F. Araujo, Carsten Blank, Adenilton José da Silva

Published Nov 7, 2021• 3 citations
OpenAlex

Abstract

State preparation algorithms are routines used in many quantum computing applications, from solving a linear system of equations to quantum machine learning. In this paper, we present an exact state preparation algorithm that considers entanglement to reduce the complexity of the generated quantum circuit. The proposed method allows approximation by entanglement reduction. The approximation of an entangled state by two separable states allows a quadratic decrease in the number of CNOT gates in exchange for an approximation error. Through experimental analysis with 7-qubits devices, the approximation error observed through measurements is smaller than the error due to the noise generated by the circuit to prepare the original state.

Related papers

Quantum State Preparation Using an Exact CNOT Synthesis Formulation

Hanyu Wang, Jason Cong, Giovanni De Micheli

Minimizing the use of CNOT gates in quantum state preparation is a crucial step in quantum compilation, as they introduce coupling constraints and more noise than single-qubit gates. Reducing the number of CNOT gates can lead to more efficient and accurate quantum computations. However, the attainment of optimal solutions is hindered by the complexity of modeling superposition and entanglement. In this paper, we propose an effective state preparation algorithm using an exact CNOT synthesis formulation. Our method represents a milestone as the first design automation algorithm to surpass manual design, reducing the best CNOT count to prepare a Dicke state by 2x. For general states with up to 20 qubits, our method reduces the CNOT count by 9% and 32% for dense and sparse states, respectively, on average, compared to the latest algorithms.

arXiv:2401.01009•Design, Automation, and Test in Europe•Mar 25, 2024•5 citations

Quantum-state preparation with universal gate decompositions

Martin Plesch, Časlav Brukner

In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of $2$. It also reduces the total number of cnot gates from ${2}^{n}$ to $\frac{23}{24}{2}^{n}$ in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from $11$ cnot gates to $9$ and the depth from $11$ to $5$ steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.

arXiv:1003.5760•Physical Review A•Mar 3, 2011•335 citations

Approximate State Preparation for Noisy Quantum Computers

Tom Rindell

Any quantum computation begins with some process of state preparation where the prepared state functions as the input value for the computation. For most states, preparation becomes exceedingly more demanding as the number of qubits increases. Moreover, the noise present in the gate operations further complicates the process by contributing to the decoherence of the state. This thesis studies possible approaches to address these problems. For a reader not familiar with the basic principles of quantum computing, Chapter 2 should provide a sufficient summary in order to follow through the rest of the thesis. In Chapter 3 a standard method of state preparation is presented in detail for 2 and 4-qubit cases and then generalized for an arbitrary number of qubits. However in order to present a comprehensive coverage, the necessary gate decompositions for state preparation are first presented and proved. The number of required quantum gates for the preparation of a general state increases exponentially in the number of qubits. Each gate introduces a small error in the computation, the cumulative effect of which can make the decoherence in the final state very severe. Therefore it is perhaps more suitable to prepare a less complex approximation of the target state with fewer gates to obtain better fidelity in the presence of noise. For this purpose, two methods are presented: low-rank state preparation algorithm (LRSP) and a genetic algorithm. LRSP provides a systematic way to generate circuits for approximate state preparation; however, for any given state LRSP can make only very specific approximations, giving us a very limited range of circuits to work with. For this reason our work introduces a genetic algorithm to iterate over the LRSP circuits and to provide a wider range of candidate circuits for approximate state preparation. Using this approach we prepared a range of approximate state preparation circuits for 1000 different Haar-random states and ran them with simulated noise on IBM Qiskit FakeVigo backend. We found that the numerical results matched closely with our theoretical prediction and showed that when run on a noisy quantum computer, the highest fidelity is obtained not for the exact state preparation circuit but for a shorter approximate circuit.

Työväentutkimus Vuosikirja•Oct 25, 2025•0 citations

Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications

Xiao‐Ming Zhang, Tongyang Li, Xiao Yuan

Quantum state preparation is an important subroutine for quantum computing. We show that any n-qubit quantum state can be prepared with a Θ(n)-depth circuit using only single- and two-qubit gates, although with a cost of an exponential amount of ancillary qubits. On the other hand, for sparse quantum states with d⩾2 nonzero entries, we can reduce the circuit depth to Θ(log(nd)) with O(ndlogd) ancillary qubits. The algorithm for sparse states is exponentially faster than best-known results and the number of ancillary qubits is nearly optimal and only increases polynomially with the system size. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories, and find cases with exponential reductions of the circuit depth for all these three tasks. In particular, using our algorithm, we find a family of linear system solving problems enjoying exponential speedups, even compared to the best-known quantum and classical dequantization algorithms.

arXiv:2201.11495•Physical Review Letters•Nov 30, 2022•176 citations

Low-Rank Quantum State Preparation

Israel F. Araujo, Carsten Blank, Ismael C. S. Araújo +1 more

Ubiquitous in quantum computing is the step to encode data into a quantum state. This process is called quantum state preparation, and its complexity for nonstructured data is exponential on the number of qubits. Several works address this problem, for instance, by using variational methods that train a fixed depth circuit with manageable complexity. These methods have their limitations, as the lack of a back-propagation technique and barren plateaus. This work proposes an algorithm to reduce state preparation circuit depth by offloading computational complexity to a classical computer. The initialized quantum state can be exact or an approximation, and we show that the approximation is better on today’s quantum processors than the initialization of the original state. Experimental evaluation demonstrates that the proposed method enables more efficient initialization of probability distributions in a quantum state.

arXiv:2111.03132•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Jul 21, 2023•29 citations

On Actual Preparation of Dicke State on a Quantum Computer

Chandra Sekhar Mukherjee, Subhamoy Maitra, Vineet Gaurav +1 more

The exact number of CNOT and single qubit gates needed to implement a Quantum Algorithm in a given architecture is one of the central problems of Quantum Computation. In this work we study the importance of concise realizations of Partially defined Unitary Transformations for better circuit construction using the case study of Dicke State Preparation. The Dicke States $(\left|D^n_k \right>)$ are an important class of entangled states with uses in many branches of Quantum Information. In this regard we provide the most efficient Deterministic Dicke State Preparation Circuit in terms of CNOT and single qubit gate counts in comparison to existing literature. We further observe that our improvements also reduce architectural constraints of the circuits. We implement the circuit for preparing $\left| D^4_2 \right>$ on the "ibmqx2" machine of the IBM QX service and observe that the error induced due to noise in the system is lesser in comparison to the existing circuit descriptions. We conclude by describing the CNOT map of the generic $\left| D^n_k \right>$ preparation circuit and analyze different ways of distributing the CNOT gates in the circuit and its affect on the induced error.

arXiv:2007.01681•Jul 3, 2020•4 citations
State preparation algorithms are routines used in many quantum computing applications, from solving a linear system of equations to quantum machine learning. In this paper, we present an exact state preparation algorithm that considers entanglement to reduce the complexity of the generated quantum circuit. The proposed method allows approximation by entanglement reduction. The approximation of an entangled state by two separable states allows a quadratic decrease in the number of CNOT gates in exchange for an approximation error. Through experimental analysis with 7-qubits devices, the approximation error observed through measurements is smaller than the error due to the noise generated by the circuit to prepare the original state.
Minimizing the use of CNOT gates in quantum state preparation is a crucial step in quantum compilation, as they introduce coupling constraints and more noise than single-qubit gates. Reducing the number of CNOT gates can lead to more efficient and accurate quantum computations. However, the attainment of optimal solutions is hindered by the complexity of modeling superposition and entanglement. In this paper, we propose an effective state preparation algorithm using an exact CNOT synthesis formulation. Our method represents a milestone as the first design automation algorithm to surpass manual design, reducing the best CNOT count to prepare a Dicke state by 2x. For general states with up to 20 qubits, our method reduces the CNOT count by 9% and 32% for dense and sparse states, respectively, on average, compared to the latest algorithms.
In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of 222. It also reduces the total number of cnot gates from 2n{2}^{n}2n to 23242n\frac{23}{24}{2}^{n}2423​2n in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from 111111 cnot gates to 999 and the depth from 111111 to 555 steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.
Any quantum computation begins with some process of state preparation where the prepared state functions as the input value for the computation. For most states, preparation becomes exceedingly more demanding as the number of qubits increases. Moreover, the noise present in the gate operations further complicates the process by contributing to the decoherence of the state. This thesis studies possible approaches to address these problems. For a reader not familiar with the basic principles of quantum computing, Chapter 2 should provide a sufficient summary in order to follow through the rest of the thesis. In Chapter 3 a standard method of state preparation is presented in detail for 2 and 4-qubit cases and then generalized for an arbitrary number of qubits. However in order to present a comprehensive coverage, the necessary gate decompositions for state preparation are first presented and proved. The number of required quantum gates for the preparation of a general state increases exponentially in the number of qubits. Each gate introduces a small error in the computation, the cumulative effect of which can make the decoherence in the final state very severe. Therefore it is perhaps more suitable to prepare a less complex approximation of the target state with fewer gates to obtain better fidelity in the presence of noise. For this purpose, two methods are presented: low-rank state preparation algorithm (LRSP) and a genetic algorithm. LRSP provides a systematic way to generate circuits for approximate state preparation; however, for any given state LRSP can make only very specific approximations, giving us a very limited range of circuits to work with. For this reason our work introduces a genetic algorithm to iterate over the LRSP circuits and to provide a wider range of candidate circuits for approximate state preparation. Using this approach we prepared a range of approximate state preparation circuits for 1000 different Haar-random states and ran them with simulated noise on IBM Qiskit FakeVigo backend. We found that the numerical results matched closely with our theoretical prediction and showed that when run on a noisy quantum computer, the highest fidelity is obtained not for the exact state preparation circuit but for a shorter approximate circuit.
Quantum state preparation is an important subroutine for quantum computing. We show that any n-qubit quantum state can be prepared with a Θ(n)-depth circuit using only single- and two-qubit gates, although with a cost of an exponential amount of ancillary qubits. On the other hand, for sparse quantum states with d⩾2 nonzero entries, we can reduce the circuit depth to Θ(log(nd)) with O(ndlogd) ancillary qubits. The algorithm for sparse states is exponentially faster than best-known results and the number of ancillary qubits is nearly optimal and only increases polynomially with the system size. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories, and find cases with exponential reductions of the circuit depth for all these three tasks. In particular, using our algorithm, we find a family of linear system solving problems enjoying exponential speedups, even compared to the best-known quantum and classical dequantization algorithms.
Ubiquitous in quantum computing is the step to encode data into a quantum state. This process is called quantum state preparation, and its complexity for nonstructured data is exponential on the number of qubits. Several works address this problem, for instance, by using variational methods that train a fixed depth circuit with manageable complexity. These methods have their limitations, as the lack of a back-propagation technique and barren plateaus. This work proposes an algorithm to reduce state preparation circuit depth by offloading computational complexity to a classical computer. The initialized quantum state can be exact or an approximation, and we show that the approximation is better on today’s quantum processors than the initialization of the original state. Experimental evaluation demonstrates that the proposed method enables more efficient initialization of probability distributions in a quantum state.
The exact number of CNOT and single qubit gates needed to implement a Quantum Algorithm in a given architecture is one of the central problems of Quantum Computation. In this work we study the importance of concise realizations of Partially defined Unitary Transformations for better circuit construction using the case study of Dicke State Preparation. The Dicke States (∣Dkn>)(\left|D^n_k \right>)(∣Dkn​⟩) are an important class of entangled states with uses in many branches of Quantum Information. In this regard we provide the most efficient Deterministic Dicke State Preparation Circuit in terms of CNOT and single qubit gate counts in comparison to existing literature. We further observe that our improvements also reduce architectural constraints of the circuits. We implement the circuit for preparing ∣D24>\left| D^4_2 \right>​D24​⟩ on the "ibmqx2" machine of the IBM QX service and observe that the error induced due to noise in the system is lesser in comparison to the existing circuit descriptions. We conclude by describing the CNOT map of the generic ∣Dkn>\left| D^n_k \right>∣Dkn​⟩ preparation circuit and analyze different ways of distributing the CNOT gates in the circuit and its affect on the induced error.