Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1909.11485 · Nature Physics

Classical algorithms for quantum mean values

Sergey B. Bravyi, David Gosset, Ramis Movassagh

Published Jan 4, 2021• 92 citations
arXivHTMLPDF
DOI
10.1038/s41567-020-01109-8

Related papers

Quantum Circuit for Calculating Mean Values Via Grover-like Algorithm

Robert R. Tucci

In this paper, we give a quantum circuit for calculating the mean value of a function $A(x^n)\in \mathbb{C}$, where $x^n\in \{0,1\}^n$. Known classical algorithms for calculating the mean value of a structureless function $A(x^n)$ take ${\cal O}(2^n)$ steps. Our quantum algorithm is based on a Grover-like algorithm and it takes ${\cal O}(\sqrt{2^n})$ steps. Our algorithm differs significantly from previously proposed quantum algorithms for calculating the mean value of a function via Grover's algorithm.

arXiv:1404.0668•Mar 31, 2014•3 citations

Basic Quantum Algorithms

Eduardo R. Mucciolo

CRC Press eBooks•Aug 6, 2025•0 citations

Quantum-Classical Hybrid Algorithms

Belal Ehsan Baaquie, L. C. Kwek

Springer eBooks•Jan 1, 2023•4 citations

Quantum mean-value approximator for hard integer-value problems

David Joseph, Antonio Martinez, Cong Ling +1 more

The quantum mean value (QMV) problem is a classically difficult problem that is the central part of many quantum algorithms. We show that using an approximation instead of the exact expectation results in a quadratic improvement in the efficiency of QMV and thus the underlying quantum algorithm. Together with efficient classical sampling algorithms, a quantum algorithm with minimal gate count can thus improve the efficiency of algorithms to solve general integer-value problems, such as the shortest vector problem investigated in this work.

arXiv:2105.13106•Physical Review A•May 13, 2022•4 citations

Classical Algorithm for the Mean Value problem over Short-Time Hamiltonian Evolutions

Reyhaneh Aghaei Saem, Ali Hamed Moosavian

Simulating physical systems has been an important application of classical and quantum computers. In this article we present an efficient classical algorithm for simulating time-dependent quantum mechanical Hamiltonians over constant periods of time. The algorithm presented here computes the mean value of an observable over the output state of such short-time Hamiltonian evolutions. In proving the performance of this algorithm we use Lieb-Robinson type bounds to limit the evolution of local operators within a lightcone. This allows us to divide the task of simulating a large quantum system into smaller systems that can be handled on normal classical computers.

arXiv:2301.11420•Jan 26, 2023•1 citation

On quantum algorithms

CleveRichard, EkertArtur, HendersonLea +2 more

Complexity•Sep 1, 1998•0 citations
In this paper, we give a quantum circuit for calculating the mean value of a function A(xn)∈CA(x^n)\in \mathbb{C}A(xn)∈C, where xn∈{0,1}nx^n\in \{0,1\}^nxn∈{0,1}n. Known classical algorithms for calculating the mean value of a structureless function A(xn)A(x^n)A(xn) take O(2n){\cal O}(2^n)O(2n) steps. Our quantum algorithm is based on a Grover-like algorithm and it takes O(2n){\cal O}(\sqrt{2^n})O(2n​) steps. Our algorithm differs significantly from previously proposed quantum algorithms for calculating the mean value of a function via Grover's algorithm.
The quantum mean value (QMV) problem is a classically difficult problem that is the central part of many quantum algorithms. We show that using an approximation instead of the exact expectation results in a quadratic improvement in the efficiency of QMV and thus the underlying quantum algorithm. Together with efficient classical sampling algorithms, a quantum algorithm with minimal gate count can thus improve the efficiency of algorithms to solve general integer-value problems, such as the shortest vector problem investigated in this work.
Simulating physical systems has been an important application of classical and quantum computers. In this article we present an efficient classical algorithm for simulating time-dependent quantum mechanical Hamiltonians over constant periods of time. The algorithm presented here computes the mean value of an observable over the output state of such short-time Hamiltonian evolutions. In proving the performance of this algorithm we use Lieb-Robinson type bounds to limit the evolution of local operators within a lightcone. This allows us to divide the task of simulating a large quantum system into smaller systems that can be handled on normal classical computers.