Efficient quantum algorithms for state measurement and linear algebra applications

DOI10.1142/S021974991850048XMaRDI QIDQ4620263zbMATH OpenOpenAlexFDO

Authors Apoorva Patel, Anjani Priyadarsini

Publication date 8 February 2019

Published in International Journal of Quantum Information (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.01984

zbMATH Keywords

computational complexityChebyshev polynomialsNewton-Raphson methoddigital representationquantum simulations

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Best approximation, Chebyshev systems (41A50) Newton-type methods (49M15) Quantum measurement theory, state operations, state preparations (81P15)

Abstract: We present an algorithm for measurement of $k$-local operators in a quantum state, which scales logarithmically both in the system size and the output accuracy. The key ingredients of the algorithm are a digital representation of the quantum state, and a decomposition of the measurement operator in a basis of operators with known discrete spectra. We then show how this algorithm can be combined with (a) Hamiltonian evolution to make quantum simulations efficient, (b) the Newton-Raphson method based solution of matrix inverse to efficiently solve linear simultaneous equations, and (c) Chebyshev expansion of matrix exponentials to efficiently evaluate thermal expectation values. The general strategy may be useful in solving many other linear algebra problems efficiently.

Recommendations

• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Efficient Algorithms for Universal Quantum Simulation
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Faster ground state preparation and high-precision ground energy estimation with fewer qubits

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 3814037 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Adiabatic quantum state generation and statistical zero knowledge
• Faster algorithms via approximation theory
• Mathematical methods for physicists. A comprehensive guide
• Methods of conjugate gradients for solving linear systems
• Modern computer arithmetic
• Numerical recipes. The art of scientific computing.
• Universal Quantum Simulators

Cited in

(14)

• Computing scalar products via a two-terminal quantum transmission line
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Book review of: R. J. Lipton and K. W. Regan, Quantum algorithms via linear algebra. A primer
• Paulicomposer: compute tensor products of Pauli matrices efficiently
• Measuring 4-local qubit observables could probabilistically solve PSPACE
• Efficient quantum algorithms to construct arbitrary Dicke states
• Superlinear advantage for exact quantum algorithms
• An efficient quantum algorithm for spectral estimation
• An improved method for quantum matrix multiplication
• Quantum algorithm for preparing the ground state of a physical system through multi-step quantum resonant transitions
• Quantum algorithm for matrix logarithm by integral formula
• Efficient quantum algorithm for similarity measures for molecules
• Quantum linear system algorithm applied to communication systems
• Quantum relaxed row and column iteration methods based on block-encoding

This page was built for publication: Efficient quantum algorithms for state measurement and linear algebra applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4620263)