Estimating quantum amplitudes can be exponentially improved

• URL: http://arxiv.org/abs/2408.13721v2
• Date: Sun, 08 Dec 2024 04:21:21 GMT
• Title: Estimating quantum amplitudes can be exponentially improved
• Authors: Zhong-Xia Shang, Qi Zhao,
• Abstract summary: Estimating quantum amplitude (the overlap between two quantum states) is a fundamental task in quantum computing. We present a novel algorithmic framework for estimating quantum amplitudes by transforming pure states into matrix forms. Our framework achieves the standard quantum limit $epsilon-2$ and the Heisenberg limit $epsilon-1$, respectively.
• Score: 11.282486674587236
• License:
• Abstract: Estimating quantum amplitude (the overlap between two quantum states) is a fundamental task in quantum computing and serves as a core subroutine in numerous quantum algorithms. In this work, we present a novel algorithmic framework for estimating quantum amplitudes by transforming pure states into matrix forms and encoding them into non-diagonal blocks of density operators and diagonal blocks of unitary operators. Our framework presents two specific estimation protocols, achieving the standard quantum limit $\epsilon^{-2}$ and the Heisenberg limit $\epsilon^{-1}$, respectively. Whenever one quantum state is prepared by a $\mathit{o}(n)$-depth quantum circuit and the other has a large entanglement under a certain bi-partition, our algorithm can give exponential improvement over the direct Hadamard test and amplitude estimation algorithm for both query complexity and gate complexity. The gate complexity reduction comes from a new technique called channel block encoding. This technique provides a systematical and efficient way to embed the matrix form of a pure state into a density operator.

Related papers

• Purest Quantum State Identification [13.974066377698044]
  We design methods for identifying the purest one within $K$ unknown $n$-qubit quantum states using $N$ samples. This framework provides concrete design principles for overcoming sampling bottlenecks in quantum technologies.
  arXiv  Detail & Related papers  (2025-02-20T07:42:16Z)
• The Algorithm for Solving Quantum Linear Systems of Equations With Coherent Superposition and Its Extended Applications [8.8400072344375]
  We propose two quantum algorithms for solving quantum linear systems of equations with coherent superposition. The two quantum algorithms can both compute the rank and general solution by one measurement. Our analysis indicates that the proposed algorithms are mainly suitable for conducting attacks against lightweight symmetric ciphers.
  arXiv  Detail & Related papers  (2024-05-11T03:03:14Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• 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 State Preparation and Non-Unitary Evolution with Diagonal Operators [0.0]
  We present a dilation based algorithm to simulate non-unitary operations on unitary quantum devices. We use this algorithm to prepare random sub-normalized two-level states on a quantum device with high fidelity. We also present the accurate non-unitary dynamics of two-level open quantum systems in a dephasing channel and an amplitude damping channel computed on a quantum device.
  arXiv  Detail & Related papers  (2022-05-05T17:56:41Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Automatic quantum circuit encoding of a given arbitrary quantum state [0.0]
  We propose a quantum-classical hybrid algorithm to encode a given arbitrarily quantum state onto an optimal quantum circuit. The proposed algorithm employs as an objective function the absolute value of fidelity $F = langle 0 vert hatmathcalCdagger vert Psi rangle$. We experimentally demonstrate that a quantum circuit generated by the AQCE algorithm can indeed represent the original quantum state reasonably on a noisy real quantum device.
  arXiv  Detail & Related papers  (2021-12-29T12:33:41Z)
• K-sparse Pure State Tomography with Phase Estimation [1.2183405753834557]
  Quantum state tomography (QST) for reconstructing pure states requires exponentially increasing resources and measurements with the number of qubits. QST reconstruction for any pure state composed of the superposition of $K$ different computational basis states of $n$bits in a specific measurement set-up is presented.
  arXiv  Detail & Related papers  (2021-11-08T09:43:12Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• 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.