© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2411.04019 · Physical Review X

Low-Depth Quantum Symmetrization

Zhenning Liu, Andrew M. Childs, Daniel Gottesman

Published Jul 20, 2026• 2 citations

Abstract

Quantum symmetrization is the task of transforming a nonstrictly increasing list of n integers into an equal superposition of all permutations of the list (or more generally, performing this operation coherently on a superposition of such lists). This task plays a key role in initial state preparation for first-quantized simulations. Motivated by an application to fermionic systems, various algorithms have been proposed to solve a weaker version of symmetrization in which the input list is increasing, but the general symmetrization problem with repetitions in the input list has not been well studied. We present the first efficient quantum algorithms for the general symmetrization problem. If m is the greatest possible value of the input list, our first algorithm symmetrizes any single classical input list using O ˜ ( log n ) depth and O ( n log n + log m ) ancilla qubits, and our second algorithm symmetrizes an arbitrary superposition of input lists using O ˜ ( log 3 n ) depth and O ( n log n ) ancilla qubits. Our algorithms enable efficient simulation of bosonic quantum systems in first quantization (in particular, we describe a simulation of the Bose-Hubbard model with complexity poly ( n , log m ) ) and can prepare (superpositions of) Dicke states of any Hamming weight in O ˜ ( log n ) depth (respectively, O ˜ ( log 3 n ) depth) using O ( n log n ) ancilla qubits. We also propose an O ˜ ( log 3 n ) -depth quantum algorithm to transform second-quantized states to first-quantized states. Using this algorithm, QFT-based quantum telescope arrays can image brighter photon sources, extending quantum interferometric imaging systems to a new regime.

DOI: 10.1103/9qhy-ms2y

Related papers

Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions

Wei Zi, Pei Yuan, Junhong Nie +1 more

Hamming weight computation maps an $n$-bit input to the number of ones it contains. It is a basic subroutine in quantum computing, and the core building block for symmetric Boolean functions, whose value depends only on the Hamming weight of the input. Moreover, symmetric Boolean functions are among the most common primitives in quantum computing. Efficient circuits for both problems are therefore important for the efficiency of many quantum algorithms. We study the depth-ancilla tradeoffs of Hamming weight computation under two qubit connectivity models, all-to-all and two-dimensional nearest-neighbor square grid (2D), in both the standard and dynamic circuit models. In the standard all-to-all model, we obtain depth $O(\log n)$ with a sublinear number of ancillas. In the standard 2D model, we give a circuit of depth $O(\sqrt n)$ with $O(\log^2 n)$ ancillas, and a matching lower bound showing that $Θ(\sqrt n)$ is optimal. In both dynamic models, we obtain constant-depth circuits with $O(n^{1+\varepsilon}\operatorname{polylog}\,n)$ ancillary qubits for every fixed $\varepsilon>0$. All constructions give a smooth depth-ancilla tradeoff, and they also extend to arbitrary symmetric Boolean functions.

quant-pharXiv:2608.04627•Aug 6, 2026•0 citations

Efficient classical algorithms for simulating symmetric quantum systems

Eric R. Anschuetz, Andreas Bauer, Bobak T. Kiani +1 more

In light of recently proposed quantum algorithms that incorporate symmetries in the hope of quantum advantage, we show that with symmetries that are restrictive enough, classical algorithms can efficiently emulate their quantum counterparts given certain classical descriptions of the input. Specifically, we give classical algorithms that calculate ground states and time-evolved expectation values for permutation-invariant Hamiltonians specified in the symmetrized Pauli basis with runtimes polynomial in the system size. We use tensor-network methods to transform symmetry-equivariant operators to the block-diagonal Schur basis that is of polynomial size, and then perform exact matrix multiplication or diagonalization in this basis. These methods are adaptable to a wide range of input and output states including those prescribed in the Schur basis, as matrix product states, or as arbitrary quantum states when given the power to apply low depth circuits and single qubit measurements.

Quantum•Nov 28, 2023•27 citations

Efficient classical algorithms for simulating symmetric quantum systems

Eric R. Anschuetz, Bauer, Andreas, Bobak T. Kiani +1 more

In light of recently proposed quantum algorithms that incorporate symmetries in the hope of quantum advantage, we show that with symmetries that are restrictive enough, classical algorithms can efficiently emulate their quantum counterparts given certain classical descriptions of the input. Specifically, we give classical algorithms that calculate ground states and time-evolved expectation values for permutation-invariant Hamiltonians specified in the symmetrized Pauli basis with runtimes polynomial in the system size. We use tensor-network methods to transform symmetry-equivariant operators to the block-diagonal Schur basis that is of polynomial size, and then perform exact matrix multiplication or diagonalization in this basis. These methods are adaptable to a wide range of input and output states including those prescribed in the Schur basis, as matrix product states, or as arbitrary quantum states when given the power to apply low depth circuits and single qubit measurements.

arXiv:2211.16998•Nov 30, 2022•1 citation

Preparation and Compression of Symmetric Pure Quantum States

Andreas Bärtschi

Symmetric under permutation of the qubits.All terms with the same Hamming Weight must have the same amplitude: ⇒ Dicke States |D n k are equal superpositions of all HW-k strings.⇒ They form an orthonormal basis for symmetric pure states.Efficient in terms of Circuit Model: Deterministic Scheme, Linear Nearest Neighbor architecture.Small total number of Gates: O(n 2 ) many.Shallow Depth: O(n) steps.

•Feb 19, 2024•0 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.

quant-pharXiv:2511.11227•Nov 17, 2025•0 citations

Optimal Fermion-Qubit Mappings via Quadratic Assignment

Mitchell Chiew, Cameron Ibrahim, Ilya Safro +1 more

Simulation of fermionic systems is one of the most promising applications of quantum computers. It spans problems in quantum chemistry, high-energy physics and condensed matter. Underpinning the core steps of any quantum simulation algorithm, fermion-qubit mappings translate the fermionic interactions to the operators and states of quantum computers. This translation is highly non-trivial: a burgeoning supply of fermion-qubit mappings has arisen over the past twenty years to address the limited resources of early quantum technology. Previous literature has presented a dichotomy between ancillafree fermion-qubit mappings, which minimise qubit count, and local encodings, which minimise gate complexity. We present two computational approaches to the construction of general mappings while working with a limited number of qubits, striking a balance between the low-qubit and low-gate demands of present quantum technology. The first method frames the order of fermionic labels as an instance of the quadratic assignment problem to minimize the total and maximum Pauli weights in a problem Hamiltonian. We compare the orderoptimized performance of several common ancilla-free mappings on systems of size up to 225 fermionic modes. The second method is a computational approach to incrementally add ancilla qubits to Jordan-Wigner transformations and further reduce the Pauli weights. By adding up to 10 ancilla qubits, we were able to reduce the total Pauli weight by as much as 67 % in JordanWigner transformations of fermionic systems with up to 64 modes, outperforming the previous state-of-the-art ancilla-free mappings. Reproducibility: source code and data are available at https://github.com/cameton/QCE_QubitAssignment

arXiv:2504.21636•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•1 citation

Quantum symmetrization is the task of transforming a nonstrictly increasing list of n integers into an equal superposition of all permutations of the list (or more generally, performing this operation coherently on a superposition of such lists). This task plays a key role in initial state preparation for first-quantized simulations. Motivated by an application to fermionic systems, various algorithms have been proposed to solve a weaker version of symmetrization in which the input list is increasing, but the general symmetrization problem with repetitions in the input list has not been well studied. We present the first efficient quantum algorithms for the general symmetrization problem. If m is the greatest possible value of the input list, our first algorithm symmetrizes any single classical input list using O ˜ ( log n ) depth and O ( n log n + log m ) ancilla qubits, and our second algorithm symmetrizes an arbitrary superposition of input lists using O ˜ ( log 3 n ) depth and O ( n log n ) ancilla qubits. Our algorithms enable efficient simulation of bosonic quantum systems in first quantization (in particular, we describe a simulation of the Bose-Hubbard model with complexity poly ( n , log m ) ) and can prepare (superpositions of) Dicke states of any Hamming weight in O ˜ ( log n ) depth (respectively, O ˜ ( log 3 n ) depth) using O ( n log n ) ancilla qubits. We also propose an O ˜ ( log 3 n ) -depth quantum algorithm to transform second-quantized states to first-quantized states. Using this algorithm, QFT-based quantum telescope arrays can image brighter photon sources, extending quantum interferometric imaging systems to a new regime.

Hamming weight computation maps an

n

-bit input to the number of ones it contains. It is a basic subroutine in quantum computing, and the core building block for symmetric Boolean functions, whose value depends only on the Hamming weight of the input. Moreover, symmetric Boolean functions are among the most common primitives in quantum computing. Efficient circuits for both problems are therefore important for the efficiency of many quantum algorithms. We study the depth-ancilla tradeoffs of Hamming weight computation under two qubit connectivity models, all-to-all and two-dimensional nearest-neighbor square grid (2D), in both the standard and dynamic circuit models. In the standard all-to-all model, we obtain depth

O(\log n)

with a sublinear number of ancillas. In the standard 2D model, we give a circuit of depth

O(\sqrt n)

with

O(\log^2 n)

ancillas, and a matching lower bound showing that

Θ(\sqrt n)

is optimal. In both dynamic models, we obtain constant-depth circuits with

O(n^{1+\varepsilon}\operatorname{polylog}\,n)

ancillary qubits for every fixed

\varepsilon>0

. All constructions give a smooth depth-ancilla tradeoff, and they also extend to arbitrary symmetric Boolean functions.

In light of recently proposed quantum algorithms that incorporate symmetries in the hope of quantum advantage, we show that with symmetries that are restrictive enough, classical algorithms can efficiently emulate their quantum counterparts given certain classical descriptions of the input. Specifically, we give classical algorithms that calculate ground states and time-evolved expectation values for permutation-invariant Hamiltonians specified in the symmetrized Pauli basis with runtimes polynomial in the system size. We use tensor-network methods to transform symmetry-equivariant operators to the block-diagonal Schur basis that is of polynomial size, and then perform exact matrix multiplication or diagonalization in this basis. These methods are adaptable to a wide range of input and output states including those prescribed in the Schur basis, as matrix product states, or as arbitrary quantum states when given the power to apply low depth circuits and single qubit measurements.

In light of recently proposed quantum algorithms that incorporate symmetries in the hope of quantum advantage, we show that with symmetries that are restrictive enough, classical algorithms can efficiently emulate their quantum counterparts given certain classical descriptions of the input. Specifically, we give classical algorithms that calculate ground states and time-evolved expectation values for permutation-invariant Hamiltonians specified in the symmetrized Pauli basis with runtimes polynomial in the system size. We use tensor-network methods to transform symmetry-equivariant operators to the block-diagonal Schur basis that is of polynomial size, and then perform exact matrix multiplication or diagonalization in this basis. These methods are adaptable to a wide range of input and output states including those prescribed in the Schur basis, as matrix product states, or as arbitrary quantum states when given the power to apply low depth circuits and single qubit measurements.

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.

Simulation of fermionic systems is one of the most promising applications of quantum computers. It spans problems in quantum chemistry, high-energy physics and condensed matter. Underpinning the core steps of any quantum simulation algorithm, fermion-qubit mappings translate the fermionic interactions to the operators and states of quantum computers. This translation is highly non-trivial: a burgeoning supply of fermion-qubit mappings has arisen over the past twenty years to address the limited resources of early quantum technology. Previous literature has presented a dichotomy between ancillafree fermion-qubit mappings, which minimise qubit count, and local encodings, which minimise gate complexity. We present two computational approaches to the construction of general mappings while working with a limited number of qubits, striking a balance between the low-qubit and low-gate demands of present quantum technology. The first method frames the order of fermionic labels as an instance of the quadratic assignment problem to minimize the total and maximum Pauli weights in a problem Hamiltonian. We compare the orderoptimized performance of several common ancilla-free mappings on systems of size up to 225 fermionic modes. The second method is a computational approach to incrementally add ancilla qubits to Jordan-Wigner transformations and further reduce the Pauli weights. By adding up to 10 ancilla qubits, we were able to reduce the total Pauli weight by as much as 67 % in JordanWigner transformations of fermionic systems with up to 64 modes, outperforming the previous state-of-the-art ancilla-free mappings. Reproducibility: source code and data are available at https://github.com/cameton/QCE_QubitAssignment