Preparation of Hamming-Weight-Preserving Quantum States with Log-Depth Quantum Circuits

• URL: http://arxiv.org/abs/2508.14470v1
• Date: Wed, 20 Aug 2025 06:50:13 GMT
• Title: Preparation of Hamming-Weight-Preserving Quantum States with Log-Depth Quantum Circuits
• Authors: Yu Li, Guojing Tian, Xiaoyu He, Xiaoming Sun,
• Abstract summary: We focus on the Hamming-Weight-preserving states, defined as $psi_textHr = sum_textHW(x)=k alpha_x |xrangle$, which have leveraged their strength in quantum machine learning.<n>We propose an algorithm to build the preparation circuit of $O(log n)$-depth with $O(m)$ ancillary qubits.<n>Specifically for the $n$-qubit tree-structured and grid-structured states, the number of ancillary qubits in the corresponding preparation circuits
• Score: 20.069035622098905
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum state preparation is a critical task in quantum computing, particularly in fields such as quantum machine learning, Hamiltonian simulation, and quantum algorithm design. The depth of preparation circuit for the most general state has been optimized to approximately optimal, but the log-depth appears only when the number of ancillary qubits reaches exponential. Actually, few log-depth preparation algorithms assisted by polynomial ancillary qubits have been come up with even for a certain kind of non-uniform state. We focus on the Hamming-Weight-preserving states, defined as $|\psi_{\text{H}}\rangle = \sum_{\text{HW}(x)=k} \alpha_x |x\rangle$, which have leveraged their strength in quantum machine learning. Especially when $k=2$, such Hamming-Weight-preserving states correspond to simple undirected graphs and will be called graph-structured states. Firstly, for the $n$-qubit general graph-structured states with $m$ edges, we propose an algorithm to build the preparation circuit of $O(\log n)$-depth with $O(m)$ ancillary qubits. Specifically for the $n$-qubit tree-structured and grid-structured states, the number of ancillary qubits in the corresponding preparation circuits can be optimized to zero. Next we move to the preparation for the HWP states with $k\geq 3$, and it can be solved in $O(\log{{n \choose k}})$-depth using $O\left({n \choose k}\right)$ ancillary qubits, while the size keeps $O\big( {n \choose k} \big)$. These depth and size complexities, for any $k \geq 2$, exactly coincide with the lower bounds of $\Omega (\log{{n \choose k}})$-depth and $\Omega ({n \choose k})$-size that we prove lastly, which confirms the near-optimal efficiency of our algorithms.

Related papers

• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• Depth-Efficient Quantum Circuit Synthesis for Deterministic Dicke State Preparation [5.755460769073285]
  Dicke states represent an important class of entangled quantum states with broad applications in quantum computing.<n>We propose deterministic quantum circuits for Dicke state preparation under two commonly seen qubit connectivity constraints.
  arXiv  Detail & Related papers  (2025-05-21T11:55:17Z)
• Quantum oracles for the finite element method [45.200826131319815]
  This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N times N stiffness and mass matrices.<n>We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
  arXiv  Detail & Related papers  (2025-04-28T14:28:31Z)
• Nearly Optimal Circuit Size for Sparse Quantum State Preparation [0.0]
  A quantum state is said to be $d$-sparse if it has only $d$ non-zero amplitudes.<n>We prove for the first time a trade-off between the number of ancillary qubits and the circuit size.
  arXiv  Detail & Related papers  (2024-06-23T15:28:20Z)
• Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
  We consider the preparation for $n$-qubit sparse quantum states with $s$ non-zero amplitudes and propose two algorithms. The first algorithm uses $O(ns/log n + n)$ gates, improving upon previous methods by $O(log n)$. The second algorithm is tailored for binary strings that exhibit a short Hamiltonian path.
  arXiv  Detail & Related papers  (2024-04-08T02:13:40Z)
• Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
  We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. We present a quantum algorithm that uses $O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$ queries to the block-encoding for any $Gamma$.
  arXiv  Detail & Related papers  (2024-04-04T17:58:01Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis [24.555887999356646]
  The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth and size complexity remain open when ancillary qubits are available. In this paper, we study efficient constructions of quantum circuits with $m$ ancillary qubits that can prepare $psi_vrangle$ in depth. Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide range of parameter regime.
  arXiv  Detail & Related papers  (2021-08-13T09:47:11Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.