Estimating quantum amplitudes can be exponentially improved

• URL: http://arxiv.org/abs/2408.13721v1
• Date: Sun, 25 Aug 2024 04:35:53 GMT
• Title: Estimating quantum amplitudes can be exponentially improved
• Authors: Zhong-Xia Shang, Qi Zhao,
• Abstract summary: Estimating quantum amplitudes is a fundamental task in quantum computing. We present a novel framework for estimating quantum amplitudes by transforming pure states into their matrix forms. Our framework achieves the standard quantum limit $epsilon-2$ and the Heisenberg limit $epsilon-1$, respectively.
• Score: 11.282486674587236
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Estimating quantum amplitudes 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 their matrix forms and encoding them into density matrices and unitary operators. Our framework presents two specific estimation protocols, achieving the standard quantum limit $\epsilon^{-2}$ and the Heisenberg limit $\epsilon^{-1}$, respectively. Our approach significantly reduces the complexity of estimation when states exhibit specific entanglement properties. We also introduce a new technique called channel block encoding for preparing density matrices, providing optimal constructions for gate-based quantum circuits and Hamiltonian simulations. The framework yields considerable advancements contingent on circuit depth or simulation time. A minimum of superpolynomial improvement can be achieved when the depth or the time is within the range of $\mathcal{O}(\text{poly}\log(n))$. Moreover, in certain extreme cases, an exponential improvement can be realized. Based on our results, various complexity-theoretic implications are discussed.

Related papers

• Schrödingerization based Quantum Circuits for Maxwell's Equation with time-dependent source terms [24.890270804373824]
  This paper explicitly constructs a quantum circuit for Maxwell's equations with perfect electric conductor (PEC) boundary conditions. We show that quantum algorithms constructed using Schr"odingerisation exhibit acceleration in computational complexity compared to the classical Finite Difference Time Domain (FDTD) format.
  arXiv  Detail & Related papers  (2024-11-17T08:15:37Z)
• Entropy-driven entanglement forging [0.0]
  We show how entropy-driven entanglement forging can be used to adjust quantum simulations to the limitations of noisy intermediate-scale quantum devices. Our findings indicate that our method, entropy-driven entanglement forging, can be used to adjust quantum simulations to the limitations of noisy intermediate-scale quantum devices.
  arXiv  Detail & Related papers  (2024-09-06T16:54:41Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum quench dynamics as a shortcut to adiabaticity [31.114245664719455]
  We develop and test a quantum algorithm in which the incorporation of a quench step serves as a remedy to the diverging adiabatic timescale. Our experiments show that this approach significantly outperforms the adiabatic algorithm.
  arXiv  Detail & Related papers  (2024-05-31T17:07:43Z)
• Quantivine: A Visualization Approach for Large-scale Quantum Circuit Representation and Analysis [31.203764035373677]
  We develop Quantivine, an interactive system for exploring and understanding quantum circuits. A series of novel circuit visualizations are designed to uncover contextual details such as qubit provenance, parallelism, and entanglement. The effectiveness of Quantivine is demonstrated through two usage scenarios of quantum circuits with up to 100 qubits.
  arXiv  Detail & Related papers  (2023-07-18T04:51:28Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Improved maximum-likelihood quantum amplitude estimation [0.0]
  Quantum estimation is a key subroutine in a number of powerful quantum algorithms, including quantum-enhanced Monte Carlo simulation and quantum machine learning. In this article, we deepen the analysis of Maximum-likelihood quantum amplitude estimation (MLQAE) to put the algorithm in a more prescriptive form, including scenarios where quantum circuit depth is limited. We then propose and numerically validate a modification to the algorithm to overcome this problem, bringing the algorithm even closer to being useful as a practical subroutine on near- and mid-term quantum hardware.
  arXiv  Detail & Related papers  (2022-09-07T17:30:37Z)
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices [3.1952399274829775]
  We develop a tool called quantum eigenvalue transformation of unitary matrices with reals (QET-U) This leads to a simple quantum algorithm that outperforms all previous algorithms with a comparable circuit structure for estimating the ground state energy. We demonstrate the performance of the algorithm using IBM Qiskit for the transverse field Ising model.
  arXiv  Detail & Related papers  (2022-04-12T17:11:40Z)
• 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)
• A Grand Unification of Quantum Algorithms [0.0]
  A number of quantum algorithms were recently tied together by a technique known as the quantum singular value transformation. This paper provides a tutorial through these developments, first illustrating how quantum signal processing may be generalized to the quantum eigenvalue transform. We then employ QSVT to construct intuitive quantum algorithms for search, phase estimation, and Hamiltonian simulation.
  arXiv  Detail & Related papers  (2021-05-06T17:46:33Z)

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.