Low-depth quantum symmetrization

• URL: http://arxiv.org/abs/2411.04019v2
• Date: Fri, 02 May 2025 19:03:14 GMT
• Title: Low-depth quantum symmetrization
• Authors: Zhenning Liu, Andrew M. Childs, Daniel Gottesman,
• Abstract summary: We present the first efficient quantum algorithms for the general symmetrization problem.<n>Our algorithms enable efficient simulation of bosonic quantum systems in first quantization.<n>We also propose an $tildeO(log3 n)$-depth quantum algorithm to transform second-quantized states to first-quantized states.
• Score: 1.5566524830295307
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum symmetrization is the task of transforming a non-strictly 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 strictly 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 $\tilde{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 $\tilde{O}(\log^3 n)$ depth and $O(n\log n)$ ancilla qubits. Our algorithms enable efficient simulation of bosonic quantum systems in first quantization and can prepare (superpositions of) Dicke states of any Hamming weight in $\tilde{O}(\log n)$ depth (respectively, $\tilde{O}(\log^3 n)$ depth) using $O(n\log n)$ ancilla qubits. We also propose an $\tilde{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.

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)
• Preparation of Hamming-Weight-Preserving Quantum States with Log-Depth Quantum Circuits [20.069035622098905]
  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
  arXiv  Detail & Related papers  (2025-08-20T06:50:13Z)
• Matrix encoding method in variational quantum singular value decomposition [49.494595696663524]
  Conditional measurement is involved to avoid small success probability in ancilla measurement. The objective function for the algorithm can be obtained probabilistically via measurement of the state of a one-qubit subsystem.
  arXiv  Detail & Related papers  (2025-03-19T07:01:38Z)
• Quantum algorithm for the gradient of a logarithm-determinant [0.0]
  The inverse of a sparse-rank input operator may be determined efficiently.<n>Measuring an expectation value of the quantum state--instead of all $N2$ elements of the input operator--can be accomplished in $O(ksigma)$ time.<n>The algorithm is envisioned for fully error-corrected quantum computers but may be implementable on near-term machines.
  arXiv  Detail & Related papers  (2025-01-16T09:39:31Z)
• Resource-efficient algorithm for estimating the trace of quantum state powers [1.5133368155322298]
  Estimating the trace of quantum state powers, $textTr(rhok)$, for $k$ identical quantum states is a fundamental task. We introduce an algorithm that requires only $mathcalO(tilder)$ qubits and $mathcalO(tilder)$ multi-qubit gates. We extend our algorithm to the estimation of $textTr(rhok)$ for arbitrary observables and $textTr(rhok)
  arXiv  Detail & Related papers  (2024-08-01T06:23:52Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• 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)
• Towards multiqudit quantum processor based on a $^{171}$Yb$^{+}$ ion string: Realizing basic quantum algorithms [29.67699443799741]
  We demonstrate a quantum processor based on a 3D linear Paul trap that uses $171$Yb$+$ ions with 8 individually controllable four-level qudits (ququarts) The design of the developed ion trap provides high secular, low heating rate, which, together with individual addressing and readout optical systems, allows executing quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-05T15:48:43Z)
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an $(N-1)times (N-1)$ matrix.<n>The basic idea is to encode each row of the matrix into a pure state of some quantum system.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• Variational-quantum-eigensolver-inspired optimization for spin-chain work extraction [39.58317527488534]
  Energy extraction from quantum sources is a key task to develop new quantum devices such as quantum batteries. One of the main issues to fully extract energy from the quantum source is the assumption that any unitary operation can be done on the system. We propose an approach to optimize the extractable energy inspired by the variational quantum eigensolver (VQE) algorithm.
  arXiv  Detail & Related papers  (2023-10-11T15:59:54Z)
• Non-Linear Transformations of Quantum Amplitudes: Exponential Improvement, Generalization, and Applications [0.0]
  Quantum algorithms manipulate the amplitudes of quantum states to find solutions to computational problems. We present a framework for applying a general class of non-linear functions to the amplitudes of quantum states. Our work provides an important and efficient building block with potentially numerous applications in areas such as optimization, state preparation, quantum chemistry, and machine learning.
  arXiv  Detail & Related papers  (2023-09-18T14:57:21Z)
• 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)
• Fast Quantum Algorithms for Trace Distance Estimation [8.646488471216262]
  We propose efficient quantum algorithms for estimating the trace distance within additive error $varepsilon$ between mixed quantum states of rank $r$. We show that the decision version of low-rank trace distance estimation is $mathsfBQP$-complete.
  arXiv  Detail & Related papers  (2023-01-17T10:16:14Z)
• 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)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum Approximate Counting for Markov Chains and Application to Collision Counting [0.0]
  We show how to generalize the quantum approximate counting technique developed by Brassard, Hoyer and Tapp [ICALP 1998] to estimating the number of marked states of a Markov chain. This makes it possible to construct quantum approximate counting algorithms from quantum search algorithms based on the powerful "quantum walk based search" framework established by Magniez, Nayak, Roland and Santha.
  arXiv  Detail & Related papers  (2022-04-06T03:04:42Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications [10.436969366019015]
  We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits. 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.
  arXiv  Detail & Related papers  (2022-01-27T13:16:30Z)
• Quantum Algorithm for Fidelity Estimation [8.270684567157987]
  For two unknown mixed quantum states $rho$ and $sigma$ in an $N$-dimensional space, computing their fidelity $F(rho,sigma)$ is a basic problem. We propose a quantum algorithm that solves this problem in $namepoly(log (N), r, 1/varepsilon)$ time.
  arXiv  Detail & Related papers  (2021-03-16T13:57:01Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• 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.