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

IEEE Transactions on Quantum Engineering

Efficient Boolean Methods for Preparing Uniform Quantum States

Fereshte Mozafari, Heinz Riener, Mathias Soeken, Giovanni De Micheli

Published Jan 1, 2021• 17 citations
Publisher

Abstract

As each quantum algorithm requires a specific initial quantum state, quantum state preparation is an important task in quantum computing. The preparation of quantum states is performed by a quantum circuit consisting of controlled-NOT (CNOT) and single-qubit gates. Known algorithms to prepare arbitrary$n$-qubit quantum states create quantum circuits in$O(2^n)$runtime and use$O(2^n)$CNOTs, which are more expensive than single-qubit gates in NISQ architectures. To reduce runtime and the number of CNOTs, we simplify the problem by considering an important family of quantum states, which areuniform quantum states(UQSs). We map UQSs to Boolean functions and propose aUQS preparation(UQSP) method. Preparing UQSs using Boolean functions allows us to utilize different representations of Boolean functions. We utilize decision diagrams to reduce runtime and enable preparation for a larger number of qubits where the state-of-the-art methods are not applicable. To further reduce the number of CNOTs, we utilize variable reordering and functional dependencies among the variables. Our state preparation method requires an exponential number of CNOTs in the worst case but it reduces CNOTs significantly for practical benchmarks. Moreover, our method generates an exact representation of quantum states without using free-qubits. We compare our algorithm with QisKit. The comparison shows that our UQSP method is capable to reduce the average number of CNOTs by 75.31% for the practical benchmarks. The runtime is almost reduced by a factor of 2.

DOI
10.1109/tqe.2021.3101663

Related papers

Efficient deterministic preparation of quantum states using decision diagrams

Fereshte Mozafari, Giovanni De Micheli, Yuxiang Yang

Loading classical data into quantum registers is one of the most important primitives of quantum computing. While the complexity of preparing a generic quantum state is exponential in the number of qubits, in many practical tasks the state to prepare has a certain structure that allows for faster preparation. In this paper, we consider quantum states that can be efficiently represented by (reduced) decision diagrams, a versatile data structure for the representation and analysis of Boolean functions. We design an algorithm that utilizes the structure of decision diagrams to prepare their associated quantum states. Our algorithm has a circuit complexity that is linear in the number of paths in the decision diagram. Numerical experiments show that our algorithm reduces the circuit complexity by up to 31.85% compared to the state-of-the-art algorithm, when preparing generic $n$-qubit states with ${n}^{3}$ nonzero amplitudes. Additionally, for states with sparse decision diagrams, including the initial state of the quantum Byzantine agreement protocol, our algorithm reduces the number of controlled-nots by 86.61--99.9%.

arXiv:2206.08588•Physical Review A•Aug 29, 2022•22 citations

Automatic Uniform Quantum State Preparation Using Decision Diagrams

Fereshte Mozafari, Mathias Soeken, Heinz Riener +1 more

Most quantum algorithms assume some specific initial state in superposition of basis states before performing the desired application-specific computations. The preparation of such states itself requires a computation performed by a quantum circuit. In this paper, we investigate the automatic state preparation of a specific subset of quantum states that are uniform superpositions over a subset of basis states, called uniform quantum states. We exploit that such states can be represented using Boolean functions and present a recursive algorithm based on functional decomposition. When using binary decision diagrams as function representation, we can enable fast and scalable quantum state preparation with respect to the size of the decision diagram. We show that the algorithm can find quantum circuits for functions, where state-of-the-art algorithms cannot be applied anymore.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•Nov 1, 2020•10 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

Preparing Dicke States on a Quantum Computer

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

Exact requirement of controlled NOT (CNOT) and single-qubit gates to implement a quantum algorithm in a given architecture is one of the central problems in this computational paradigm. In this article, we take a tutorial approach in explaining the preparation of Dicke states (|Dkn〉) using concise realizations of partially defined unitary transformations. We show how to efficiently implement the state-of-the-art deterministic Dicke state preparation circuits and in turn optimize them in terms of CNOT and single-qubit gate counts. We explain theoretical ideas in reducing the gate counts and observe how these improvements are reflected in actual implementation of the circuits. To emphasize the advantages, we describe the circuit for preparing |D24〉 on the “ibmqx2” machine of the IBM quantum experience (QX) service. Our approach shows that the error induced due to noise in the system is lesser in comparison to the existing works. We conclude by describing the CNOT map of the generic |Dkn〉 preparation circuit and analyze different ways of distributing the CNOT gates in the circuit and its effect on the induced error in the Noisy Intermediate Scale Quantum environment.

IEEE Transactions on Quantum Engineering•Jan 1, 2020•38 citations

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

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
As each quantum algorithm requires a specific initial quantum state, quantum state preparation is an important task in quantum computing. The preparation of quantum states is performed by a quantum circuit consisting of controlled-NOT (CNOT) and single-qubit gates. Known algorithms to prepare arbitrarynnn-qubit quantum states create quantum circuits inO(2n)O(2^n)O(2n)runtime and useO(2n)O(2^n)O(2n)CNOTs, which are more expensive than single-qubit gates in NISQ architectures. To reduce runtime and the number of CNOTs, we simplify the problem by considering an important family of quantum states, which areuniform quantum states(UQSs). We map UQSs to Boolean functions and propose aUQS preparation(UQSP) method. Preparing UQSs using Boolean functions allows us to utilize different representations of Boolean functions. We utilize decision diagrams to reduce runtime and enable preparation for a larger number of qubits where the state-of-the-art methods are not applicable. To further reduce the number of CNOTs, we utilize variable reordering and functional dependencies among the variables. Our state preparation method requires an exponential number of CNOTs in the worst case but it reduces CNOTs significantly for practical benchmarks. Moreover, our method generates an exact representation of quantum states without using free-qubits. We compare our algorithm with QisKit. The comparison shows that our UQSP method is capable to reduce the average number of CNOTs by 75.31% for the practical benchmarks. The runtime is almost reduced by a factor of 2.
Loading classical data into quantum registers is one of the most important primitives of quantum computing. While the complexity of preparing a generic quantum state is exponential in the number of qubits, in many practical tasks the state to prepare has a certain structure that allows for faster preparation. In this paper, we consider quantum states that can be efficiently represented by (reduced) decision diagrams, a versatile data structure for the representation and analysis of Boolean functions. We design an algorithm that utilizes the structure of decision diagrams to prepare their associated quantum states. Our algorithm has a circuit complexity that is linear in the number of paths in the decision diagram. Numerical experiments show that our algorithm reduces the circuit complexity by up to 31.85% compared to the state-of-the-art algorithm, when preparing generic nnn-qubit states with n3{n}^{3}n3 nonzero amplitudes. Additionally, for states with sparse decision diagrams, including the initial state of the quantum Byzantine agreement protocol, our algorithm reduces the number of controlled-nots by 86.61--99.9%.
Most quantum algorithms assume some specific initial state in superposition of basis states before performing the desired application-specific computations. The preparation of such states itself requires a computation performed by a quantum circuit. In this paper, we investigate the automatic state preparation of a specific subset of quantum states that are uniform superpositions over a subset of basis states, called uniform quantum states. We exploit that such states can be represented using Boolean functions and present a recursive algorithm based on functional decomposition. When using binary decision diagrams as function representation, we can enable fast and scalable quantum state preparation with respect to the size of the decision diagram. We show that the algorithm can find quantum circuits for functions, where state-of-the-art algorithms cannot be applied anymore.
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.
Exact requirement of controlled NOT (CNOT) and single-qubit gates to implement a quantum algorithm in a given architecture is one of the central problems in this computational paradigm. In this article, we take a tutorial approach in explaining the preparation of Dicke states (|Dkn〉) using concise realizations of partially defined unitary transformations. We show how to efficiently implement the state-of-the-art deterministic Dicke state preparation circuits and in turn optimize them in terms of CNOT and single-qubit gate counts. We explain theoretical ideas in reducing the gate counts and observe how these improvements are reflected in actual implementation of the circuits. To emphasize the advantages, we describe the circuit for preparing |D24〉 on the “ibmqx2” machine of the IBM quantum experience (QX) service. Our approach shows that the error induced due to noise in the system is lesser in comparison to the existing works. We conclude by describing the CNOT map of the generic |Dkn〉 preparation circuit and analyze different ways of distributing the CNOT gates in the circuit and its effect on the induced error in the Noisy Intermediate Scale Quantum environment.
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.
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.