Efficient quantum algorithms for state measurement and linear algebra applications

DOI10.1142/S021974991850048XzbMATH Open1407.81071arXiv1710.01984OpenAlexW2964307483MaRDI QIDQ4620263FDOQ4620263

Authors: Apoorva Patel, Anjani Priyadarsini 

Publication date: 8 February 2019

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

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.

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

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

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)

Cites Work

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

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
• Superlinear advantage for exact quantum algorithms
• Efficient quantum algorithms to construct arbitrary Dicke states
• 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)