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 International Symposium on Multiple-Valued Logic (ISMVL)

Automatic Uniform Quantum State Preparation Using Decision Diagrams

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

Published Nov 1, 2020• 10 citations
Publisher

Abstract

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.

DOI
10.1109/ismvl49045.2020.00-10

Related papers

Efficient Boolean Methods for Preparing Uniform Quantum States

Fereshte Mozafari, Heinz Riener, Mathias Soeken +1 more

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.

IEEE Transactions on Quantum Engineering•Jan 1, 2021•17 citations

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

Synthesis of quantum circuits based on incompletely specified functions and if-decision diagrams

Anatoly Alekseevich Prihozhy

The problem of synthesis and optimisation of logical reversible and quantum circuits from functional descriptions represented as decision diagrams is considered. It is one of the key problems being solved with the aim of creating quantum computing technology and quantum computers. A new method of stepwise transformation of the initial functional specification to a quantum circuit is proposed, which provides for the following project states: reduced ordered binary decision diagram, if-decision diagram, functional if-decision diagram, reversible circuit and quantum circuit. The novelty of the method consists in extending the Shannon and Davio expansions of a Boolean function on a single variable to the expansions of the same Boolean function on another function with obtaining decomposition products that are represented by incompletely defined Boolean functions. Uncertainty in the decomposition products gives remarkable opportunities for minimising the graph representation of the specified function. Instead of two outgoing branches of the binary diagram vertex, three outgoing branches of the if-diagram vertex are generated, which increase the level of parallelism in reversible and quantum circuits. For each transformation step, appropriate mapping rules are proposed that reduce the number of lines, gates and the depth of the reversible and quantum circuit. The comparison of new results with the results given by the known method of mapping the vertices of binary decision diagram into cascades of reversible and quantum gates shows a significant improvement in the quality of quantum circuits that are synthesised by the proposed method.

Journal of the Belarusian State University Mathematics and Informatics•Dec 14, 2021•0 citations

Mixed-Dimensional Qudit State Preparation Using Edge-Weighted Decision Diagrams

Kevin Mato, Stefan Hillmich, Robert Wille

Quantum computers have the potential to solve important problems which are fundamentally intractable on a classical computer. The underlying physics of quantum computing platforms supports using multi-valued logic, which promises a boost in performance over the prevailing two-level logic. One key element to exploiting this potential is the capability to efficiently prepare quantum states for multi-valued, or qudit, systems. Due to the time sensitivity of quantum computers, the circuits to prepare the required states have to be as short as possible. In this paper, we investigate quantum state preparation with a focus on mixed-dimensional systems, where the individual qudits may have different dimensionalities. The proposed approach automatically realizes quantum circuits constructing a corresponding mixed-dimensional quantum state. To this end, decision diagrams are used as a compact representation of the quantum state to be realized. We further incorporate the ability to approximate the quantum state to enable a finely controlled trade-off between accuracy, memory complexity, and number of operations in the circuit. Empirical evaluations demonstrate the effectiveness of the proposed approach in facilitating fast and scalable quantum state preparation, with performance directly linked to the size of the decision diagram. The implementation is freely available as part of Munich Quantum Toolkit (MQT) at github.com/cda-tum/mqt-qudits.

arXiv:2406.03531•ACM/IEEE Design Automation Conference (DAC)•Jun 23, 2024•4 citations

Approximating Decision Diagrams for Quantum Circuit Simulation

Stefan Hillmich, Alwin Zulehner, Richard Kueng +2 more

Quantum computers promise to solve important problems faster than conventional computers ever could. Underneath is a fundamentally different computational primitive that introduces new challenges for the development of software tools that aid designers of corresponding quantum algorithms. The different computational primitives render classical simulation of quantum circuits particularly challenging. While the logic simulation of conventional circuits is comparatively simple with linear complexity with respect to the number of gates, quantum circuit simulation has to deal with the exponential memory requirements to represent quantum states on non-quantum hardware with respect to the number of qubits. Decision Diagrams (DDs) address this challenge through exploitation of redundancies in matrices and vectors to provide significantly more compact representations in many cases. Moreover, the probabilistic nature of quantum computations enables another angle to tackle the complexity: Quantum algorithms are resistant to some degree against small inaccuracies in the quantum state as these only lead to small changes in the outcome probabilities. We propose to exploit this resistance against (small) errors to gain even more compact decision diagrams. In this work, we investigate the potential of approximation in quantum circuit simulation in detail. To this end, we first present four dedicated schemes that exploit the error resistance and efficiently approximate quantum states represented by decision diagrams. Subsequently, we propose two simulation strategies that utilize those approximations schemes in order to improve the efficiency of DD-based quantum circuit simulation, while, at the same time, allowing the user to control the resulting degradation in accuracy. We empirically show that the proposed approximation schemes reduce the size of decision diagrams substantially and also analytically prove the effect of multiple approximations on the attained accuracy. Eventually, this enables speed-ups of the resulting approximate quantum circuit simulation of up to several orders of magnitudes—again, while controlling the fidelity of the result.

ACM Transactions on Quantum Computing•Apr 25, 2022•14 citations

Quantum state preparation via free binary decision diagram

Yu Tanaka, Hayata Yamasaki, Mio Murao

Abstract Quantum state preparation (QSP) is the task of preparing a quantum state from a given classical description. The classical description of an n -qubit quantum state may have exp ⁡ ( O ( n ) ) parameters in general, which makes preparing the corresponding state inherently inefficient in the worst case. However, in many practical cases, we may be able to employ suitable data structures for QSP. Ordered binary decision diagrams (OBDDs) and free BDDs (FBDDs) are data structures that can represent large-scale data in a compressed way. An efficient QSP method for a subclass of OBDDs is known, but requires an O ( 2 n ) -sized quantum circuit in general, while QSP based on FBDDs, which includes OBDDs as a special case, remains unexplored. Here, we construct a state-preparation procedure for QSP when the classical description of a quantum state is given by an FBDD with weighted edges and analyze the space and time complexity of QSP in this setting. We provide a nontrivial example of an n -qubit state that can be represented by a weighted FBDD (WFBDD) with N = O ( poly ( n ) ) nodes rather than exp ( O ( n ) ) . We show that any quantum state represented by a QSP-admissible WFBDD with N nodes can be prepared by an O ( N ) -sized quantum circuit using at most N ancillary qubits, exponentially improving the required circuit size for QSP compared to other BDD-based QSPs. We also provide another example of an n -qubit state that can be represented by a WFBDD with N = O ( n 2 ) nodes and O ( n 2 ) ancillary qubits, for which the known amplitude-amplification-based QSP cost expression is exponential in n . These results provide techniques to employ FBDDs

arXiv:2407.01671•Journal of Physics A Mathematical and Theoretical•Jun 11, 2026•0 citations
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.
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%.
The problem of synthesis and optimisation of logical reversible and quantum circuits from functional descriptions represented as decision diagrams is considered. It is one of the key problems being solved with the aim of creating quantum computing technology and quantum computers. A new method of stepwise transformation of the initial functional specification to a quantum circuit is proposed, which provides for the following project states: reduced ordered binary decision diagram, if-decision diagram, functional if-decision diagram, reversible circuit and quantum circuit. The novelty of the method consists in extending the Shannon and Davio expansions of a Boolean function on a single variable to the expansions of the same Boolean function on another function with obtaining decomposition products that are represented by incompletely defined Boolean functions. Uncertainty in the decomposition products gives remarkable opportunities for minimising the graph representation of the specified function. Instead of two outgoing branches of the binary diagram vertex, three outgoing branches of the if-diagram vertex are generated, which increase the level of parallelism in reversible and quantum circuits. For each transformation step, appropriate mapping rules are proposed that reduce the number of lines, gates and the depth of the reversible and quantum circuit. The comparison of new results with the results given by the known method of mapping the vertices of binary decision diagram into cascades of reversible and quantum gates shows a significant improvement in the quality of quantum circuits that are synthesised by the proposed method.
Quantum computers have the potential to solve important problems which are fundamentally intractable on a classical computer. The underlying physics of quantum computing platforms supports using multi-valued logic, which promises a boost in performance over the prevailing two-level logic. One key element to exploiting this potential is the capability to efficiently prepare quantum states for multi-valued, or qudit, systems. Due to the time sensitivity of quantum computers, the circuits to prepare the required states have to be as short as possible. In this paper, we investigate quantum state preparation with a focus on mixed-dimensional systems, where the individual qudits may have different dimensionalities. The proposed approach automatically realizes quantum circuits constructing a corresponding mixed-dimensional quantum state. To this end, decision diagrams are used as a compact representation of the quantum state to be realized. We further incorporate the ability to approximate the quantum state to enable a finely controlled trade-off between accuracy, memory complexity, and number of operations in the circuit. Empirical evaluations demonstrate the effectiveness of the proposed approach in facilitating fast and scalable quantum state preparation, with performance directly linked to the size of the decision diagram. The implementation is freely available as part of Munich Quantum Toolkit (MQT) at github.com/cda-tum/mqt-qudits.
Quantum computers promise to solve important problems faster than conventional computers ever could. Underneath is a fundamentally different computational primitive that introduces new challenges for the development of software tools that aid designers of corresponding quantum algorithms. The different computational primitives render classical simulation of quantum circuits particularly challenging. While the logic simulation of conventional circuits is comparatively simple with linear complexity with respect to the number of gates, quantum circuit simulation has to deal with the exponential memory requirements to represent quantum states on non-quantum hardware with respect to the number of qubits. Decision Diagrams (DDs) address this challenge through exploitation of redundancies in matrices and vectors to provide significantly more compact representations in many cases. Moreover, the probabilistic nature of quantum computations enables another angle to tackle the complexity: Quantum algorithms are resistant to some degree against small inaccuracies in the quantum state as these only lead to small changes in the outcome probabilities. We propose to exploit this resistance against (small) errors to gain even more compact decision diagrams. In this work, we investigate the potential of approximation in quantum circuit simulation in detail. To this end, we first present four dedicated schemes that exploit the error resistance and efficiently approximate quantum states represented by decision diagrams. Subsequently, we propose two simulation strategies that utilize those approximations schemes in order to improve the efficiency of DD-based quantum circuit simulation, while, at the same time, allowing the user to control the resulting degradation in accuracy. We empirically show that the proposed approximation schemes reduce the size of decision diagrams substantially and also analytically prove the effect of multiple approximations on the attained accuracy. Eventually, this enables speed-ups of the resulting approximate quantum circuit simulation of up to several orders of magnitudes—again, while controlling the fidelity of the result.
Abstract Quantum state preparation (QSP) is the task of preparing a quantum state from a given classical description. The classical description of an n -qubit quantum state may have exp ⁡ ( O ( n ) ) parameters in general, which makes preparing the corresponding state inherently inefficient in the worst case. However, in many practical cases, we may be able to employ suitable data structures for QSP. Ordered binary decision diagrams (OBDDs) and free BDDs (FBDDs) are data structures that can represent large-scale data in a compressed way. An efficient QSP method for a subclass of OBDDs is known, but requires an O ( 2 n ) -sized quantum circuit in general, while QSP based on FBDDs, which includes OBDDs as a special case, remains unexplored. Here, we construct a state-preparation procedure for QSP when the classical description of a quantum state is given by an FBDD with weighted edges and analyze the space and time complexity of QSP in this setting. We provide a nontrivial example of an n -qubit state that can be represented by a weighted FBDD (WFBDD) with N = O ( poly ( n ) ) nodes rather than exp ( O ( n ) ) . We show that any quantum state represented by a QSP-admissible WFBDD with N nodes can be prepared by an O ( N ) -sized quantum circuit using at most N ancillary qubits, exponentially improving the required circuit size for QSP compared to other BDD-based QSPs. We also provide another example of an n -qubit state that can be represented by a WFBDD with N = O ( n 2 ) nodes and O ( n 2 ) ancillary qubits, for which the known amplitude-amplification-based QSP cost expression is exponential in n . These results provide techniques to employ FBDDs