Asymptotically Optimal Quantum Amplitude Estimation by Generalized Qubitization

• URL: http://arxiv.org/abs/2306.16695v5
• Date: Mon, 13 May 2024 11:05:41 GMT
• Title: Asymptotically Optimal Quantum Amplitude Estimation by Generalized Qubitization
• Authors: Xi Lu, Hongwei Lin,
• Abstract summary: We first show that the standard deviationally lower bounded by approximately $1.28 L-1$, where $L$ is the number of queries. Then we propose a generalized qubitization that can block-encode several functions simultaneously, and show how it can help estimating quantum amplitude to achieve the optimal accuracy.
• Score: 5.0755851789013535
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We first show that the standard deviation error of quantum amplitude estimation is asymptotically lower bounded by approximately $1.28 L^{-1}$, where $L$ is the number of queries. Then we propose a generalized qubitization that can block-encode several polynomial functions simultaneously, and show how it can help estimating quantum amplitude to achieve the optimal asymptotic accuracy, so the bound is tight.

Related papers

• Asymptotically optimal joint phase and dephasing strength estimation using spin-squeezed states [0.0]
  We show an explicit $N$-qubit protocol involving one-axis-twisted spin squeezed states.<n>The relevance of the protocol goes beyond this particular model.
  arXiv  Detail & Related papers  (2025-07-30T18:02:21Z)
• Estimating quantum amplitudes can be exponentially improved [11.282486674587236]
  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.
  arXiv  Detail & Related papers  (2024-08-25T04:35:53Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• Heisenberg-limited adaptive gradient estimation for multiple observables [0.39102514525861415]
  In quantum mechanics, measuring the expectation value of a general observable has an inherent statistical uncertainty. We provide an adaptive quantum algorithm for estimating the expectation values of $M$ general observables within root mean squared error. Our method paves a new way to precisely understand and predict various physical properties in complicated quantum systems using quantum computers.
  arXiv  Detail & Related papers  (2024-06-05T14:16:47Z)
• Two-stage Quantum Estimation and the Asymptotics of Quantum-enhanced Transmittance Sensing [2.5449435573379757]
  Quantum Cram'er-Rao bound is the ultimate limit of the mean squared error for unbiased estimation of an unknown parameter embedded in a quantum state. We apply our results to the cost of quantum-enhanced transmittance sensing.
  arXiv  Detail & Related papers  (2024-02-27T22:28:42Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Achieving metrological limits using ancilla-free quantum error-correcting codes [1.9265037496741413]
  Existing quantum error-correcting codes generally exploit entanglement between one probe and one noiseless ancilla of the same dimension. Here we construct two types of multi-probe quantum error-correcting codes, where the first one utilizes a negligible amount of ancillas and the second one is ancilla-free.
  arXiv  Detail & Related papers  (2023-03-02T00:51:02Z)
• Random-depth Quantum Amplitude Estimation [5.996131518006461]
  MLAE is a practical solution to the quantum amplitude estimation problem with Heisenberg limit error convergence. We improve MLAE by using random depths to avoid the so-called critical points, and do numerical experiments to show that our algorithm is approximately unbiased compared to the original MLAE.
  arXiv  Detail & Related papers  (2023-01-02T05:00:12Z)
• 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)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• 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)
• A hierarchy of efficient bounds on quantum capacities exploiting symmetry [8.717253904965371]
  We exploit the recently introduced $D#$ in order to obtain a hierarchy of semidefinite programming bounds on various regularized quantities. As applications, we give a general procedure to give efficient bounds on the regularized Umegaki channel divergence. We prove that for fixed input and output dimensions, the regularized sandwiched R'enyi divergence between any two quantum channels can be approximated up to an $epsilon$ accuracy in time.
  arXiv  Detail & Related papers  (2022-03-04T04:34:15Z)
• Dual-Frequency Quantum Phase Estimation Mitigates the Spectral Leakage of Quantum Algorithms [76.15799379604898]
  Quantum phase estimation suffers from spectral leakage when the reciprocal of the record length is not an integer multiple of the unknown phase. We propose a dual-frequency estimator, which approaches the Cramer-Rao bound, when multiple samples are available.
  arXiv  Detail & Related papers  (2022-01-23T17:20:34Z)
• Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
  The max-relative entropy together with its smoothed version is a basic tool in quantum information theory. We derive the exact exponent for the decay of the small modification of the quantum state in smoothing the max-relative entropy based on purified distance.
  arXiv  Detail & Related papers  (2021-11-01T16:35:41Z)

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.