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:2304.01704 · Quantum Science and Technology

Efficient parallelization of quantum basis state shift

Ljubomir Budinski, Ossi Niemimäki, Roberto Zamora-Zamora, Valtteri Lahtinen

Published Sep 18, 2023• 14 citations
arXivHTMLPDF

Abstract

Abstract Basis state shift is central to many quantum algorithms, most notably the quantum walk. Efficient implementations are of major importance for achieving a quantum speedup for computational applications. We optimize the state shift algorithm by incorporating the shift in different directions in parallel. This provides a significant reduction in the depth of the quantum circuit in comparison to the currently known methods, giving a linear scaling in the number of gates versus working qubits in contrast to the quadratic scaling of the state-of-the-art method based on the quantum Fourier transform. For a one-dimensional array of size 2 n for n > 4, we derive the total number of 15 n + 74 two-qubit CX gates in the parallel circuit, using a total of 2 n − 2 qubits including an ancilla register for the decomposition of multi-controlled gates. We focus on the one-dimensional and periodic shift, but note that the method can be extended to more complex cases.

DOI
10.1088/2058-9565/acfab7

Related papers

Parallelizing quantum circuit synthesis

Olivia Di Matteo, Michele Mosca

Quantum circuit synthesis is the process in which an arbitrary unitary operation is decomposed into a sequence of gates from a universal set, typically one which a quantum computer can implement both efficiently and fault-tolerantly. As physical implementations of quantum computers improve, the need is growing for tools that can effectively synthesize components of the circuits and algorithms they will run. Existing algorithms for exact, multi-qubit circuit synthesis scale exponentially in the number of qubits and circuit depth, leaving synthesis intractable for circuits on more than a handful of qubits. Even modest improvements in circuit synthesis procedures may lead to significant advances, pushing forward the boundaries of not only the size of solvable circuit synthesis problems, but also in what can be realized physically as a result of having more efficient circuits. We present a method for quantum circuit synthesis using deterministic walks. Also termed pseudorandom walks, these are walks in which once a starting point is chosen, its path is completely determined. We apply our method to construct a parallel framework for circuit synthesis, and implement one such version performing optimal T -count synthesis over the Clifford+ T gate set. We use our software to present examples where parallelization offers a significant speedup on the runtime, as well as directly confirm that the 4-qubit 1-bit full adder has optimal T -count 7 and T -depth 3.

arXiv:1606.07413•Quantum Science and Technology•Mar 1, 2016•42 citations

An arbitrary twoqubit computation In 23 elementary gates or less

Stephen S. Bullock, Igor L. Markov

Quantum circuits currently constitute a dominant model for quantum computation [14]. Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates [1, 9] as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worstcase upper bound of 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previously known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm [4] has a worst case of 61 gates of which 18 may be CNOTs. Our techniques rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis. They are related to the canonical decomposition of a two-qubit gate with respect to the "magic basis" of phase-shifted Bell states [11, 12]. We extend this decomposition in terms of elementary gates for quantum computation.

ACM/IEEE Design Automation Conference (DAC)•Jun 2, 2003•22 citations

An arbitrary twoqubit computation In 23 elementary gates or less

Stephen S. Bullock, Igor L. Markov

Quantum circuits currently constitute a dominant model for quantum computation [14]. Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates [1, 9] as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worstcase upper bound of 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previously known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm [4] has a worst case of 61 gates of which 18 may be CNOTs. Our techniques rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis. They are related to the canonical decomposition of a two-qubit gate with respect to the "magic basis" of phase-shifted Bell states [11, 12]. We extend this decomposition in terms of elementary gates for quantum computation.

ACM/IEEE Design Automation Conference (DAC)•Jan 1, 2003•4 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•1 citation

An arbitrary two-qubit computation in 23 elementary gates or less

Stephen S. Bullock, Igor L. Markov

Quantum circuits currently constitute a dominant model for quantum computation according to M. Nielsen and I. Chuang (2000). Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and a small number of elementary quantum gates by A. Barenco et al. (1995) and G. Song and A. Klappenecker (2003) as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worst-case upper bound to 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previous known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm according to G. Cybenko (2001) has a worst case of 61 gates of which 18 may be CNOTs. Our technique rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis. They are related to the canonical decomposition of two-qubit gate with respect to the "magic basis" of phase-shifted Bell states by N. Khaneja et al. (2001) and M. Lewenstein et al. (2001). We extend this decomposition in terms of elementary gates for quantum computation.

ACM/IEEE Design Automation Conference (DAC)•Mar 1, 2004•7 citations

Quantum circuits and parallelism

Pawan Kumar Verma, Mohit Kumar, Saurabh Singhal +1 more

This chapter develops the quantum circuit model as the operational core of gate-based quantum computation, framing circuits as structured compositions of unitary transformations acting on qubits and quantum registers. It begins by formalizing qubits as normalized state vectors in Hilbert space and extends to multi-qubit registers via tensor products, emphasizing the exponential growth of representable basis amplitudes and the resulting capacity for entanglement. Building on these foundations, this chapter details circuit design as an algorithm-engineering discipline that must balance mathematical correctness with resource efficiency under hardware and noise constraints, including circuit depth, gate count, qubit connectivity, control bandwidth, and crosstalk. Circuit construction is presented through sequential composition and parallel execution on disjoint qubit subsets, motivating scheduling methods such as dependency-graph analysis, critical-path identification, and time-slice (layer) formation under platform-imposed concurrency limits. This chapter then addresses quantum circuit decomposition as the bridge from abstract algorithmic operators to implementable gate sets, highlighting universal synthesis principles (including Solovay–Kitaev guarantees) and standard decompositions for single-qubit unitaries (Euler-angle forms) and controlled multi-qubit operations. Finally, quantum parallelism is treated as a distinctly quantum computational resource arising from superposition over 2.

CRC Press eBooks•Nov 6, 2026•0 citations
Abstract Basis state shift is central to many quantum algorithms, most notably the quantum walk. Efficient implementations are of major importance for achieving a quantum speedup for computational applications. We optimize the state shift algorithm by incorporating the shift in different directions in parallel. This provides a significant reduction in the depth of the quantum circuit in comparison to the currently known methods, giving a linear scaling in the number of gates versus working qubits in contrast to the quadratic scaling of the state-of-the-art method based on the quantum Fourier transform. For a one-dimensional array of size 2 n for n > 4, we derive the total number of 15 n + 74 two-qubit CX gates in the parallel circuit, using a total of 2 n − 2 qubits including an ancilla register for the decomposition of multi-controlled gates. We focus on the one-dimensional and periodic shift, but note that the method can be extended to more complex cases.
Quantum circuit synthesis is the process in which an arbitrary unitary operation is decomposed into a sequence of gates from a universal set, typically one which a quantum computer can implement both efficiently and fault-tolerantly. As physical implementations of quantum computers improve, the need is growing for tools that can effectively synthesize components of the circuits and algorithms they will run. Existing algorithms for exact, multi-qubit circuit synthesis scale exponentially in the number of qubits and circuit depth, leaving synthesis intractable for circuits on more than a handful of qubits. Even modest improvements in circuit synthesis procedures may lead to significant advances, pushing forward the boundaries of not only the size of solvable circuit synthesis problems, but also in what can be realized physically as a result of having more efficient circuits. We present a method for quantum circuit synthesis using deterministic walks. Also termed pseudorandom walks, these are walks in which once a starting point is chosen, its path is completely determined. We apply our method to construct a parallel framework for circuit synthesis, and implement one such version performing optimal T -count synthesis over the Clifford+ T gate set. We use our software to present examples where parallelization offers a significant speedup on the runtime, as well as directly confirm that the 4-qubit 1-bit full adder has optimal T -count 7 and T -depth 3.
Quantum circuits currently constitute a dominant model for quantum computation [14]. Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates [1, 9] as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worstcase upper bound of 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previously known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm [4] has a worst case of 61 gates of which 18 may be CNOTs. Our techniques rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis. They are related to the canonical decomposition of a two-qubit gate with respect to the "magic basis" of phase-shifted Bell states [11, 12]. We extend this decomposition in terms of elementary gates for quantum computation.
Quantum circuits currently constitute a dominant model for quantum computation [14]. Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates [1, 9] as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worstcase upper bound of 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previously known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm [4] has a worst case of 61 gates of which 18 may be CNOTs. Our techniques rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis. They are related to the canonical decomposition of a two-qubit gate with respect to the "magic basis" of phase-shifted Bell states [11, 12]. We extend this decomposition in terms of elementary gates for quantum computation.
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.
Quantum circuits currently constitute a dominant model for quantum computation according to M. Nielsen and I. Chuang (2000). Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and a small number of elementary quantum gates by A. Barenco et al. (1995) and G. Song and A. Klappenecker (2003) as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worst-case upper bound to 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previous known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm according to G. Cybenko (2001) has a worst case of 61 gates of which 18 may be CNOTs. Our technique rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis. They are related to the canonical decomposition of two-qubit gate with respect to the "magic basis" of phase-shifted Bell states by N. Khaneja et al. (2001) and M. Lewenstein et al. (2001). We extend this decomposition in terms of elementary gates for quantum computation.
This chapter develops the quantum circuit model as the operational core of gate-based quantum computation, framing circuits as structured compositions of unitary transformations acting on qubits and quantum registers. It begins by formalizing qubits as normalized state vectors in Hilbert space and extends to multi-qubit registers via tensor products, emphasizing the exponential growth of representable basis amplitudes and the resulting capacity for entanglement. Building on these foundations, this chapter details circuit design as an algorithm-engineering discipline that must balance mathematical correctness with resource efficiency under hardware and noise constraints, including circuit depth, gate count, qubit connectivity, control bandwidth, and crosstalk. Circuit construction is presented through sequential composition and parallel execution on disjoint qubit subsets, motivating scheduling methods such as dependency-graph analysis, critical-path identification, and time-slice (layer) formation under platform-imposed concurrency limits. This chapter then addresses quantum circuit decomposition as the bridge from abstract algorithmic operators to implementable gate sets, highlighting universal synthesis principles (including Solovay–Kitaev guarantees) and standard decompositions for single-qubit unitaries (Euler-angle forms) and controlled multi-qubit operations. Finally, quantum parallelism is treated as a distinctly quantum computational resource arising from superposition over 2.