Asia and South Pacific Design Automation Conference (ASP-DAC)

Efficient Preparation of Cyclic Quantum States

Fereshte Mozafari, Yuxiang Yang, Giovanni De Micheli

Published Jan 17, 2022• 1 citation

Abstract

Universal quantum algorithms that prepare arbitrary n-qubit quantum states require${O\left(2^{n}\right)}$gate complexity. The complexity can be reduced by considering specific families of quantum states depending on the task at hand. In particular, multipartite quantum states that are invariant under permutations, e.g. Dicke states, have intriguing properties. In this paper, we consider states invariant under cyclic permutations, which we call cyclic states. We present a quantum algorithm that deterministically prepares cyclic states with gate complexity${O\left(n\right)}$without requiring any ancillary qubit. Through both analytical and numerical analyses, we show that our algorithm is more efficient than existing ones.

DOI: 10.1109/asp-dac52403.2022.9712522

Related papers

Optimization and experimental realization of the quantum permutation algorithm

İ. Yalçınkaya, Z. Gedik

arXiv:1708.07900Physical Review ADec 29, 201730 citations

Constant-depth adaptive preparation of Dicke and symmetric states

Rui Luo, Junjie Chen, Xiongfeng Ma

quant-pharXiv:2608.01144Aug 4, 20260 citations

Efficient Boolean Methods for Preparing Uniform Quantum States

Fereshte Mozafari, Heinz Riener, Mathias Soeken +1 more

IEEE Transactions on Quantum EngineeringJan 1, 202117 citations

Efficient circuits for leaf-separable state preparation

Sunil Vittal, Anthony Wilkie, Nika Rastegari +2 more

quant-pharXiv:2511.11227Nov 17, 20250 citations

Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications

Xiao‐Ming Zhang, Tongyang Li, Xiao Yuan

arXiv:2201.11495Physical Review LettersNov 30, 2022176 citations

Cyclic permutations for qudits in d dimensions

Tudor-Alexandru Isdrailă, Cristian Kusko, Radu Ionicioiu

arXiv:1811.09059Scientific ReportsApr 19, 201911 citations

Asia and South Pacific Design Automation Conference (ASP-DAC)

Efficient Preparation of Cyclic Quantum States

Fereshte Mozafari, Yuxiang Yang, Giovanni De Micheli

Published Jan 17, 2022• 1 citation

Publisher

Abstract

Universal quantum algorithms that prepare arbitrary n-qubit quantum states require

{O\left(2^{n}\right)}

gate complexity. The complexity can be reduced by considering specific families of quantum states depending on the task at hand. In particular, multipartite quantum states that are invariant under permutations, e.g. Dicke states, have intriguing properties. In this paper, we consider states invariant under cyclic permutations, which we call cyclic states. We present a quantum algorithm that deterministically prepares cyclic states with gate complexity

{O\left(n\right)}

without requiring any ancillary qubit. Through both analytical and numerical analyses, we show that our algorithm is more efficient than existing ones.

DOI: 10.1109/asp-dac52403.2022.9712522

Related papers

Optimization and experimental realization of the quantum permutation algorithm

İ. Yalçınkaya, Z. Gedik

The quantum permutation algorithm provides computational speed-up over classical algorithms for determining the parity of a given cyclic permutation. For its $n$ -qubit implementations, the number of required quantum gates scales quadratically with $n$ due to the quantum Fourier transforms included. We show here for the $n$ -qubit case that the algorithm can be simplified so that it requires only $O(n)$ quantum gates, which theoretically reduces the complexity of the implementation. To test our results experimentally, we utilize IBM's 5-qubit quantum processor to realize the algorithm by using the original and simplified recipes for the 2-qubit case. It turns out that the latter results in a significantly higher success probability which allows us to verify the algorithm more precisely than the previous experimental realizations. We also verify the algorithm for the first time for the 3-qubit case with a considerable success probability by taking the advantage of our simplified scheme.The quantum permutation algorithm provides computational speed-up over classical algorithms for determining the parity of a given cyclic permutation. For its $n$-qubit implementations, the number of required quantum gates scales quadratically with $n$ due to the quantum Fourier transforms included. We show here for the $n$-qubit case that the algorithm can be simplified so that it requires only $O(n)$ quantum gates, which theoretically reduces the complexity of the implementation. To test our results experimentally, we utilize IBM's 5-qubit quantum processor to realize the algorithm by using the original and simplified recipes for the 2-qubit case. It turns out that the latter results in a significantly higher success probability which allows us to verify the algorithm more precisely than the previous experimental realizations. We also verify the algorithm for the first time for the 3-qubit case with a considerable success probability by taking the advantage of our simplified scheme.

arXiv:1708.07900Physical Review ADec 29, 201730 citations

Constant-depth adaptive preparation of Dicke and symmetric states

Rui Luo, Junjie Chen, Xiongfeng Ma

Efficient preparation of Dicke states and, more generally, permutation-symmetric states is important for quantum metrology, quantum networking, and collective quantum information processing. Measurements and classical feedforward enable low-depth preparations of these states, with a cost of ancillary qubits. In this work, we introduce an exact constant-depth adaptive preparation protocol for arbitrary Dicke- $(n,k)$ states and further symmetric states. We first provide a protocol preparing the uniform subset superposition state, as a primitive, using constant-depth adaptive circuit with $O(k^2\log^2 n)$ ancillary qubits and success probability at least $1/k$ . This yields an exact, probabilistic, constant-depth Dicke-state preparation protocol using $O\left(n^2+k^2\log^2 n+kn\log n\log\log n\right)$ ancillary qubits. Parallel repetition suppresses the failure probability exponentially without increasing the quantum depth. Moreover, the uniform subset superposition state is also of independent interest as the uniform vertex state of the Johnson graph and as the compact uniform subset state appearing in quantum-walk and topological-data-analysis algorithms. We further establish a general lifting framework that coherently combines clean unitary Dicke-state preparation circuits to prepare arbitrary symmetric states with only polynomial ancillary overhead. Combined with recent constant-depth unitary Dicke-state constructions, this gives an exact constant-depth preparation protocol for arbitrary $n$ -qubit symmetric states using $O(n^3\sqrt{\log n})$ ancillary qubits.Efficient preparation of Dicke states and, more generally, permutation-symmetric states is important for quantum metrology, quantum networking, and collective quantum information processing. Measurements and classical feedforward enable low-depth preparations of these states, with a cost of ancillary qubits. In this work, we introduce an exact constant-depth adaptive preparation protocol for arbitrary Dicke-$(n,k)$ states and further symmetric states. We first provide a protocol preparing the uniform subset superposition state, as a primitive, using constant-depth adaptive circuit with $O(k^2\log^2 n)$ ancillary qubits and success probability at least $1/k$. This yields an exact, probabilistic, constant-depth Dicke-state preparation protocol using $O\left(n^2+k^2\log^2 n+kn\log n\log\log n\right)$ ancillary qubits. Parallel repetition suppresses the failure probability exponentially without increasing the quantum depth. Moreover, the uniform subset superposition state is also of independent interest as the uniform vertex state of the Johnson graph and as the compact uniform subset state appearing in quantum-walk and topological-data-analysis algorithms. We further establish a general lifting framework that coherently combines clean unitary Dicke-state preparation circuits to prepare arbitrary symmetric states with only polynomial ancillary overhead. Combined with recent constant-depth unitary Dicke-state constructions, this gives an exact constant-depth preparation protocol for arbitrary $n$-qubit symmetric states using $O(n^3\sqrt{\log n})$ ancillary qubits.

quant-pharXiv:2608.01144Aug 4, 20260 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.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 EngineeringJan 1, 202117 citations

Efficient circuits for leaf-separable state preparation

Sunil Vittal, Anthony Wilkie, Nika Rastegari +2 more

Efficient state preparation is a challenging and important problem in quantum computing. In this work, we present a recursive state preparation algorithm that combines logarithmic-depth Dicke state circuits with Hamming weight encoders for efficiently preparing ``leaf-separable" quantum states. The algorithm is built on binary partition trees, generalized weight distribution blocks (gWDBs), and leaf-level encoders. We evaluate the performance of the algorithm by numerically simulating it on randomly generated target states with between 4 and 15 qubits. Compared to general state preparation approaches which require $O(2^n)$ CX gates, our algorithm achieves a circuit depth of $O(k\log\frac{n}{k} + 2^k)$ and uses $O(n(k+2^k))$ two-qubit gates, where $k < n$ denotes the subtree size. We also compare implementations of the algorithm with and without the use of ancilla qubits, providing a detailed analysis of the trade-offs in circuit depth and two-qubit gate counts. These results contribute to scalable state preparation for quantum algorithms that require structured inputs such as Dicke or near-Dicke states.Efficient state preparation is a challenging and important problem in quantum computing. In this work, we present a recursive state preparation algorithm that combines logarithmic-depth Dicke state circuits with Hamming weight encoders for efficiently preparing ``leaf-separable" quantum states. The algorithm is built on binary partition trees, generalized weight distribution blocks (gWDBs), and leaf-level encoders. We evaluate the performance of the algorithm by numerically simulating it on randomly generated target states with between 4 and 15 qubits. Compared to general state preparation approaches which require $O(2^n)$ CX gates, our algorithm achieves a circuit depth of $O(k\log\frac{n}{k} + 2^k)$ and uses $O(n(k+2^k))$ two-qubit gates, where $k < n$ denotes the subtree size. We also compare implementations of the algorithm with and without the use of ancilla qubits, providing a detailed analysis of the trade-offs in circuit depth and two-qubit gate counts. These results contribute to scalable state preparation for quantum algorithms that require structured inputs such as Dicke or near-Dicke states.

quant-pharXiv:2511.11227Nov 17, 20250 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.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.11495Physical Review LettersNov 30, 2022176 citations

Cyclic permutations for qudits in d dimensions

Tudor-Alexandru Isdrailă, Cristian Kusko, Radu Ionicioiu

Abstract One of the main challenges in quantum technologies is the ability to control individual quantum systems. This task becomes increasingly difficult as the dimension of the system grows. Here we propose a general setup for cyclic permutations Xd in d dimensions, a major primitive for constructing arbitrary qudit gates. Using orbital angular momentum states as a qudit, the simplest implementation of the Xd gate in d dimensions requires a single quantum sorter Sd and two spiral phase plates. We then extend this construction to a generalised Xd(p) gate to perform a cyclic permutation of a set of d, equally spaced values {| ${{\boldsymbol{\ell }}}_{{\bf{0}}}$ ℓ 0 〉, | ${{\boldsymbol{\ell }}}_{{\bf{0}}}$ ℓ 0 + p〉, …, | ${{\boldsymbol{\ell }}}_{{\bf{0}}}$ ℓ 0 + (d − 1)p〉} $\mapsto$ ↦ {| ${{\boldsymbol{\ell }}}_{{\bf{0}}}$ ℓ 0 + p〉, | ${{\boldsymbol{\ell }}}_{{\bf{0}}}$ ℓ 0 + 2p〉, …, | ${{\boldsymbol{\ell }}}_{{\bf{0}}}$ ℓ 0 〉}. We find compact implementations for the generalised Xd(p) gate in both Michelson (one sorter Sd, two spiral phase plates) and Mach-Zehnder configurations (two sorters Sd, two spiral phase plates). Remarkably, the number of spiral phase plates is independent of the qudit dimension d. Our architecture for Xd and generalised Xd(p) gate will enable complex quantum algorithms for qudits, for example quantum protocols using photonic OAM states.Abstract One of the main challenges in quantum technologies is the ability to control individual quantum systems. This task becomes increasingly difficult as the dimension of the system grows. Here we propose a general setup for cyclic permutations Xd in d dimensions, a major primitive for constructing arbitrary qudit gates. Using orbital angular momentum states as a qudit, the simplest implementation of the Xd gate in d dimensions requires a single quantum sorter Sd and two spiral phase plates. We then extend this construction to a generalised Xd(p) gate to perform a cyclic permutation of a set of d, equally spaced values {| $${{\boldsymbol{\ell }}}_{{\bf{0}}}$$ ℓ 0 〉, | $${{\boldsymbol{\ell }}}_{{\bf{0}}}$$ ℓ 0 + p〉, …, | $${{\boldsymbol{\ell }}}_{{\bf{0}}}$$ ℓ 0 + (d − 1)p〉} $$\mapsto $$ ↦ {| $${{\boldsymbol{\ell }}}_{{\bf{0}}}$$ ℓ 0 + p〉, | $${{\boldsymbol{\ell }}}_{{\bf{0}}}$$ ℓ 0 + 2p〉, …, | $${{\boldsymbol{\ell }}}_{{\bf{0}}}$$ ℓ 0 〉}. We find compact implementations for the generalised Xd(p) gate in both Michelson (one sorter Sd, two spiral phase plates) and Mach-Zehnder configurations (two sorters Sd, two spiral phase plates). Remarkably, the number of spiral phase plates is independent of the qudit dimension d. Our architecture for Xd and generalised Xd(p) gate will enable complex quantum algorithms for qudits, for example quantum protocols using photonic OAM states.

arXiv:1811.09059Scientific ReportsApr 19, 201911 citations

Universal quantum algorithms that prepare arbitrary n-qubit quantum states require

{O\left(2^{n}\right)}

{O\left(n\right)}

without requiring any ancillary qubit. Through both analytical and numerical analyses, we show that our algorithm is more efficient than existing ones.

The quantum permutation algorithm provides computational speed-up over classical algorithms for determining the parity of a given cyclic permutation. For its

n

-qubit implementations, the number of required quantum gates scales quadratically with

n

due to the quantum Fourier transforms included. We show here for the

n

-qubit case that the algorithm can be simplified so that it requires only

O(n)

quantum gates, which theoretically reduces the complexity of the implementation. To test our results experimentally, we utilize IBM's 5-qubit quantum processor to realize the algorithm by using the original and simplified recipes for the 2-qubit case. It turns out that the latter results in a significantly higher success probability which allows us to verify the algorithm more precisely than the previous experimental realizations. We also verify the algorithm for the first time for the 3-qubit case with a considerable success probability by taking the advantage of our simplified scheme.

(n,k)

states and further symmetric states. We first provide a protocol preparing the uniform subset superposition state, as a primitive, using constant-depth adaptive circuit with

O(k^2\log^2 n)

ancillary qubits and success probability at least

1/k

. This yields an exact, probabilistic, constant-depth Dicke-state preparation protocol using

O\left(n^2+k^2\log^2 n+kn\log n\log\log n\right)

ancillary qubits. Parallel repetition suppresses the failure probability exponentially without increasing the quantum depth. Moreover, the uniform subset superposition state is also of independent interest as the uniform vertex state of the Johnson graph and as the compact uniform subset state appearing in quantum-walk and topological-data-analysis algorithms. We further establish a general lifting framework that coherently combines clean unitary Dicke-state preparation circuits to prepare arbitrary symmetric states with only polynomial ancillary overhead. Combined with recent constant-depth unitary Dicke-state constructions, this gives an exact constant-depth preparation protocol for arbitrary

n

-qubit symmetric states using

O(n^3\sqrt{\log n})

ancillary qubits.

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.

O(2^n)

CX gates, our algorithm achieves a circuit depth of

O(k\log\frac{n}{k} + 2^k)

and uses

O(n(k+2^k))

two-qubit gates, where

k < n

denotes the subtree size. We also compare implementations of the algorithm with and without the use of ancilla qubits, providing a detailed analysis of the trade-offs in circuit depth and two-qubit gate counts. These results contribute to scalable state preparation for quantum algorithms that require structured inputs such as Dicke or near-Dicke states.

{{\boldsymbol{\ell }}}_{{\bf{0}}}

ℓ 0 〉, |

{{\boldsymbol{\ell }}}_{{\bf{0}}}

ℓ 0 + p〉, …, |

{{\boldsymbol{\ell }}}_{{\bf{0}}}

ℓ 0 + (d − 1)p〉}

\mapsto

↦ {|

{{\boldsymbol{\ell }}}_{{\bf{0}}}

ℓ 0 + p〉, |

{{\boldsymbol{\ell }}}_{{\bf{0}}}

ℓ 0 + 2p〉, …, |

{{\boldsymbol{\ell }}}_{{\bf{0}}}

ℓ 0 〉}. We find compact implementations for the generalised Xd(p) gate in both Michelson (one sorter Sd, two spiral phase plates) and Mach-Zehnder configurations (two sorters Sd, two spiral phase plates). Remarkably, the number of spiral phase plates is independent of the qudit dimension d. Our architecture for Xd and generalised Xd(p) gate will enable complex quantum algorithms for qudits, for example quantum protocols using photonic OAM states.