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:2409.05618 · ACM Transactions on Quantum Computing

Quantum Multiplexer Simplification for State Preparation

José Alex de Carvalho, Carlos A. Batista, Tiago M. L. Veras, Israel F. Araujo, Adenilton José da Silva

Published Jul 9, 2025• 5 citations
arXivHTMLPDF

Abstract

The initialization of quantum states or Quantum State Preparation (QSP) is a basic subroutine in quantum algorithms. In the worst case, general QSP algorithms are expensive due to the application of multi-controlled gates required to build the quantum state. Here, we propose an algorithm that detects whether a given quantum state can be factored into substates, increasing the efficiency of compiling the QSP circuit when we initialize states with some level of unentanglement. The simplification is done by eliminating controls of quantum multiplexers, significantly reducing circuit depth and the number of CNOT gates with a better execution and compilation time than the previous QSP algorithms. Considering efficiency in terms of depth and number of CNOT gates, our method is competitive with the methods in the literature. However, when it comes to run-time and compilation efficiency, our result is significantly better, and the experiments show that by increasing the number of qubits, the gap between the temporal efficiency of the methods increases.

DOI
10.1145/3748260

Related papers

Automated Circuit Depth Reduction of Quantum Subroutines via Compilation

Folkert de Ronde, Stephan Wong, Sebastian Feld

Optimizing quantum circuits by reducing circuit depth is essential for improving the efficiency and scalability of quantum algorithms, particularly as quantum hardware continues to evolve. This can be achieved by restructuring quantum algorithms to allow more parallelism. A compiler is needed to automatically detect and apply these optimizations. In this work, we focus on the optimization of two fundamental quantum subroutines: GHZ state creation and CNOT/CZ chain decomposition. Traditional implementations of these subroutines suffer from linearly increasing circuit depth, which limits scalability. We propose a compiler-driven approach that automatically detects and optimizes these two fundamental quantum subroutines. Our approach reduces circuit depth through constant-depth GHZ state creation, constant depth CZ chain decomposition, and logarithmic depth recursive CNOT chain decomposition, which enhance parallel execution. Performance analysis of benchmarked algorithms shows significant reductions in depth. However, our solution also results in an increased gate count, which makes our optimization a trade-off. The gate count for the CNOT chains is doubled, where logarithmic depth reduction is achieved. The reduced circuit depth results in more efficient algorithms by reducing execution time.

quant-pharXiv:2605.04748•May 7, 2026•0 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

Algebraic Reduction to Improve an Optimally Bounded Quantum State Preparation Algorithm

Giacomo Belli, Michele Amoretti

The preparation of $n$-qubit quantum states is a cross-cutting subroutine for many quantum algorithms, and the effort to reduce its circuit complexity is a significant challenge. In the literature, the quantum state preparation algorithm by Sun et al. is known to be optimally bounded, defining the asymptotically optimal width-depth trade-off bounds with and without ancillary qubits. In this work, a simpler algebraic decomposition is proposed to separate the preparation of the real part of the desired state from the complex one, resulting in a reduction in terms of circuit depth, total gates, and CNOT count when $m$ ancillary qubits are available. 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. Using the PennyLane library, this new algorithm for state preparation has been implemented and tested in a simulated environment for both dense and sparse quantum states, including those that are random and of physical interest. Furthermore, its performance has been compared with that of Möttönen et al.'s algorithm, which is a de facto standard for preparing quantum states in cases where no ancillary qubits are used, highlighting interesting lines of development.

quant-pharXiv:2602.06535•Feb 9, 2026•0 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

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

Quantum State Preparation Circuit Optimization Exploiting Don't Cares

Hanyu Wang, Daniel Bochen Tan, Jason Cong

Quantum state preparation initializes the quantum registers and is essential for running quantum algorithms. Designing state preparation circuits that entangle qubits efficiently with fewer two-qubit gates enhances accuracy and alleviates coupling constraints on devices. Existing methods synthesize an initial circuit and leverage compilers to reduce the circuit's gate count while preserving the unitary equivalency. In this study, we identify numerous conditions within the quantum circuit where breaking local unitary equivalences does not alter the overall outcome of the state preparation (i.e., don't cares). We introduce a peephole optimization algorithm that identifies such unitaries for replacement in the original circuit. Exploiting these don't care conditions, our algorithm achieves a 36% reduction in the number of two-qubit gates compared to prior methods.

arXiv:2409.01418•Oct 27, 2024•3 citations
The initialization of quantum states or Quantum State Preparation (QSP) is a basic subroutine in quantum algorithms. In the worst case, general QSP algorithms are expensive due to the application of multi-controlled gates required to build the quantum state. Here, we propose an algorithm that detects whether a given quantum state can be factored into substates, increasing the efficiency of compiling the QSP circuit when we initialize states with some level of unentanglement. The simplification is done by eliminating controls of quantum multiplexers, significantly reducing circuit depth and the number of CNOT gates with a better execution and compilation time than the previous QSP algorithms. Considering efficiency in terms of depth and number of CNOT gates, our method is competitive with the methods in the literature. However, when it comes to run-time and compilation efficiency, our result is significantly better, and the experiments show that by increasing the number of qubits, the gap between the temporal efficiency of the methods increases.
Optimizing quantum circuits by reducing circuit depth is essential for improving the efficiency and scalability of quantum algorithms, particularly as quantum hardware continues to evolve. This can be achieved by restructuring quantum algorithms to allow more parallelism. A compiler is needed to automatically detect and apply these optimizations. In this work, we focus on the optimization of two fundamental quantum subroutines: GHZ state creation and CNOT/CZ chain decomposition. Traditional implementations of these subroutines suffer from linearly increasing circuit depth, which limits scalability. We propose a compiler-driven approach that automatically detects and optimizes these two fundamental quantum subroutines. Our approach reduces circuit depth through constant-depth GHZ state creation, constant depth CZ chain decomposition, and logarithmic depth recursive CNOT chain decomposition, which enhance parallel execution. Performance analysis of benchmarked algorithms shows significant reductions in depth. However, our solution also results in an increased gate count, which makes our optimization a trade-off. The gate count for the CNOT chains is doubled, where logarithmic depth reduction is achieved. The reduced circuit depth results in more efficient algorithms by reducing execution time.
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 preparation of nnn-qubit quantum states is a cross-cutting subroutine for many quantum algorithms, and the effort to reduce its circuit complexity is a significant challenge. In the literature, the quantum state preparation algorithm by Sun et al. is known to be optimally bounded, defining the asymptotically optimal width-depth trade-off bounds with and without ancillary qubits. In this work, a simpler algebraic decomposition is proposed to separate the preparation of the real part of the desired state from the complex one, resulting in a reduction in terms of circuit depth, total gates, and CNOT count when mmm ancillary qubits are available. 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. Using the PennyLane library, this new algorithm for state preparation has been implemented and tested in a simulated environment for both dense and sparse quantum states, including those that are random and of physical interest. Furthermore, its performance has been compared with that of Möttönen et al.'s algorithm, which is a de facto standard for preparing quantum states in cases where no ancillary qubits are used, highlighting interesting lines of development.
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.
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.
Quantum state preparation initializes the quantum registers and is essential for running quantum algorithms. Designing state preparation circuits that entangle qubits efficiently with fewer two-qubit gates enhances accuracy and alleviates coupling constraints on devices. Existing methods synthesize an initial circuit and leverage compilers to reduce the circuit's gate count while preserving the unitary equivalency. In this study, we identify numerous conditions within the quantum circuit where breaking local unitary equivalences does not alter the overall outcome of the state preparation (i.e., don't cares). We introduce a peephole optimization algorithm that identifies such unitaries for replacement in the original circuit. Exploiting these don't care conditions, our algorithm achieves a 36% reduction in the number of two-qubit gates compared to prior methods.