Measurement Schemes for Quantum Linear Equation Solvers

• URL: http://arxiv.org/abs/2411.00723v1
• Date: Fri, 01 Nov 2024 16:36:43 GMT
• Title: Measurement Schemes for Quantum Linear Equation Solvers
• Authors: Andrew Patterson, Leigh Lapworth,
• Abstract summary: We propose a scheme for measuring the output of QSVT matrix inversion algorithms specifically for the CFD use case. We use a Quantum Signal Processing (QSP) based amplitude estimation algorithm arxiv:2207.08628 and show how it can be combined with the QSVT matrix inversion algorithm. We also propose a measurement scheme to reduce the number of amplitudes measured in the CFD example by focusing on large amplitudes only.
• Score: 4.897636783430679
• License:
• Abstract: Solving Computational Fluid Dynamics (CFD) problems requires the inversion of a linear system of equations, which can be done using a quantum algorithm for matrix inversion arxiv:1806.01838. However, the number of shots required to measure the output of the system can be prohibitive and remove any advantage obtained by quantum computing. In this work we propose a scheme for measuring the output of QSVT matrix inversion algorithms specifically for the CFD use case. We use a Quantum Signal Processing (QSP) based amplitude estimation algorithm arxiv:2207.08628 and show how it can be combined with the QSVT matrix inversion algorithm. We perform a detailed resource estimation of the amount of computational resources required for a single iteration of amplitude estimation, and compare the costs of amplitude estimation with the cost of not doing amplitude estimation and measuring the whole wavefunction. We also propose a measurement scheme to reduce the number of amplitudes measured in the CFD example by focusing on large amplitudes only. We simulate the whole CFD loop, finding that thus measuring only a small number of the total amplitudes in the output vector still results in an acceptable level of overall error.

Related papers

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Quantum amplitude estimation from classical signal processing [0.0]
  We show that the problem of amplitude estimation can be mapped directly to a problem in signal processing called direction of arrival estimation. We create a phase-estimation free, parallel quantum amplitude estimation (QAE) algorithm with a total query complexity of $sim 4.9/varepsilon$ and a parallel query complexity of $sim 0.40/varepsilon$ at 95% confidence.
  arXiv  Detail & Related papers  (2024-05-23T15:31:46Z)
• 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)
• The signaling dimension in generalized probabilistic theories [48.99818550820575]
  The signaling dimension of a given physical system quantifies the minimum dimension of a classical system required to reproduce all input/output correlations of the given system. We show that it suffices to consider extremal measurements with rayextremal effects, and we bound the number of elements of any such measurement in terms of the linear dimension. For systems with a finite number of extremal effects, we recast the problem of characterizing the extremal measurements with ray-extremal effects.
  arXiv  Detail & Related papers  (2023-11-22T02:09:16Z)
• Solving Systems of Linear Equations: HHL from a Tensor Networks Perspective [39.58317527488534]
  We present an algorithm for solving systems of linear equations based on the HHL algorithm with a novel qudits methodology. We perform a quantum-inspired version on tensor networks, taking advantage of their ability to perform non-unitary operations such as projection.
  arXiv  Detail & Related papers  (2023-09-11T08:18:41Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Adaptive Algorithm for Quantum Amplitude Estimation [13.82667502131475]
  We propose an adaptive algorithm for interval estimation of amplitudes. The proposed algorithm uses a similar number of quantum queries to achieve the same level of precision. We rigorously prove that the number of oracle queries achieves $O(1/epsilon)$, i.e., a quadratic speedup over classical Monte Carlo sampling.
  arXiv  Detail & Related papers  (2022-06-16T21:11:15Z)
• Variational quantum amplitude estimation [0.0]
  In the context of Monte Carlo (MC) integration, we numerically show that shallow circuits can accurately approximate many amplitude amplification steps. We combine the variational approach with maximum likelihood amplitude estimation. To reduce the variational cost, we propose adaptive VQAE and numerically show in 6 to 12 qubit simulations that it can outperform classical MC sampling.
  arXiv  Detail & Related papers  (2021-09-08T14:47:17Z)
• Federated Edge Learning with Misaligned Over-The-Air Computation [36.39188653838991]
  Over-the-air computation (OAC) is a promising technique to realize fast model aggregation in the uplink of federated edge learning. How to design the maximum likelihood (ML) estimator in the presence of residual channel-gain mismatch and asynchronies is an open problem. This paper formulates the problem of misaligned OAC for federated edge learning and puts forth a whitened matched filtering and sampling scheme.
  arXiv  Detail & Related papers  (2021-02-26T17:19:56Z)
• Quantum Amplitude Arithmetic [20.84884678978409]
  We propose the notion of quantum amplitude arithmetic (QAA) that intent to evolve the quantum state by performing arithmetic operations on amplitude. QAA is expected to find applications in a variety of quantum algorithms.
  arXiv  Detail & Related papers  (2020-12-21T00:17:18Z)
• Amplitude estimation via maximum likelihood on noisy quantum computer [3.5462326830737805]
  We give an experimental demonstration on a superconducting IBM Quantum device. We show that the proposed maximum likelihood estimator achieves quantum speedup in the number of queries.
  arXiv  Detail & Related papers  (2020-06-29T17:44:04Z)

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.