Fetching the paper…
Reading the bibliography…
We present a novel quantum algorithm for estimating Gibbs partition functions in sublinear time with respect to the logarithm of the size of the state space.
“Monte Carlo Estimation of the Free Energy by Multistage Sampling”
J.. Valleau and D.. Card · 1972
Earlier work this paper cites.
“The Complexity of Computing the Permanent”
L.. Valiant · 1979
Earlier work this paper cites.
“Theory of Phase Transitions: Rigorous Results”
Y.. Sinai · 1982
Earlier work this paper cites.
“Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images”
S. Geman and D. Geman · 1984
Earlier work this paper cites.
“On the Statistical Analysis of Dirty Pictures”
J. Besag · 1986
Earlier work this paper cites.
“Random Generation of Combinatorial Structures from a Uniform Distribution”
M.. Jerrum, L.. Valiant and V.. Vazirani · 1986
Earlier work this paper cites.
“On the Complexity of Computing the Volume of a Polyhedron”
M.. Dyer and A. Frieze · 1988
Earlier work this paper cites.
“Computing the Volume of Convex Bodies: A Case where Randomness Provably Helps”
M.. Dyer and A. Frieze · 1991
Earlier work this paper cites.
“A Random Polynomial-Time Algorithm for Approximating the Volume of Convex Bodies”
M. Dyer, A. Frieze and R. Kannan · 1991
Earlier work this paper cites.
“Polynomial-Time Approximation Algorithms for the Ising Model”
M. Jerrum and A. Sinclair · 1993
Earlier work this paper cites.
“A Very Simple Algorithm for Estimating the Number of k-Colorings of a Low-Degree Graph”
M. Jerrum · 1995
Earlier work this paper cites.
“Quantum Measurements and the Abelian Stabilizer Problem” arXiv:quant-ph/9511026 , 1995
A. Kitaev · 1995
Earlier work this paper cites.
“The Markov Chain Monte Carlo Method: An Approach to Approximate Counting and Integration”
M. Jerrum and A. Sinclair · 1996
Earlier work this paper cites.
“Fast Quantum Algorithms for Numerical Integrals and Stochastic Processes” arXiv:quant-ph/9908083 , 1999
D.. Abrams and C.. Williams · 1999
Earlier work this paper cites.
“Lower Bounds for Quantum Computation and Communication”, 1999
A. Nayak · 1999
Earlier work this paper cites.
“The Quantum Query Complexity of Approximating the Median and Related Statistics”
A. Nayak and F. Wu · 1999
Earlier work this paper cites.
“Quantum Algorithms and Quantum Entanglement”, 1999
B.. Terhal · 1999
Earlier work this paper cites.
“Statistical Mechanics of Money”
A. Dragulescu and V.. Yakovenko · 2000
Earlier work this paper cites.
“Quantum Amplitude Amplification and Estimation”
G. Brassard, P. Høyer, M. Mosca and A. Tapp · 2002
Cited alongside, same era.
“Quantum Summation with an Application to Integration”
S. Heinrich · 2002
Cited alongside, same era.
“Glimpses of Inequalities in Probability and Statistics”
S.. Bagui and D.. Bhaumik · 2004
Cited alongside, same era.
“Statistical Learning Theory and Stochastic Optimization”
O. Catoni · 2004
Cited alongside, same era.
“A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries”
M. Jerrum, A. Sinclair and E. Vigoda · 2004
Cited alongside, same era.
“Quantum Speed-Up of Markov Chain Based Algorithms”
M. Szegedy · 2004
Cited alongside, same era.
“Quantum Rejection Sampling”
M. Ozols, M. Roetteler and J. Roland · 2013
Later among the works it cites.
“Fixed-Point Quantum Search with an Optimal Number of Queries”
T.. Yoder, G.. Low and I.. Chuang · 2014
Later among the works it cites.
“Approximation Algorithms for the Normalizing Constant of Gibbs Distributions”
M. Huber · 2015
Later among the works it cites.
“Quantum Speedup of Monte Carlo Methods”
A. Montanaro · 2015
Later among the works it cites.
“Statistical Mechanics of Lattice Systems: A Concrete Mathematical Introduction”
S. Friedli and Y. Velenik · 2017
Later among the works it cites.
A. Gilyén, S. Arunachalam and N. Wiebe · 2017
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
“Quantum Arthur–Merlin games”
C. Marriott and J. Watrous · 2005
Cited alongside, same era.
“Simulated annealing in convex bodies and an O*(n4) volume algorithm”
L. Lovász and S. Vempala · 2006
Cited alongside, same era.
“Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems”
I. Bezáková, D. Štefankovič, V.. Vazirani and E. Vigoda · 2008
Cited alongside, same era.
“Speedup via Quantum Sampling”
P. Wocjan and A. Abeyesinghe · 2008
Cited alongside, same era.
“Adaptive Simulated Annealing: A Near-Optimal Connection between Sampling and Counting”
D. Štefankovič, S. Vempala and E. Vigoda · 2009
Cited alongside, same era.
“Quantum Algorithm for Approximating Partition Functions”
P. Wocjan, C.-F. Chiang, D. Nagaj and A. Abeyesinghe · 2009
Cited alongside, same era.
Later among the works it cites.
“Quantum Signal Processing by Single-Qubit Dynamics”, 2017
G.. Low · 2017
Later among the works it cites.
“Gaussian Cooling and O ∗ ( n 3 ) O^{*}(n^{3}) Algorithms for Volume and Gaussian Volume”
B. Cousins and S. Vempala · 2018
Later among the works it cites.
“A Faster Approximation Algorithm for the Gibbs Partition Function”
V. Kolmogorov · 2018
Later among the works it cites.
“Quantum Algorithm for Estimating Volumes of Convex Bodies” arXiv:1908.03903 [quant-ph]
S. Chakrabarti, A.. Childs, S.-H. Hung, T. Li, C. Wang and X. Wu · 2019
Later among the works it cites.
“Quantum Chebyshev’s Inequality and Applications”
Y. Hamoudi and F. Magniez · 2019
Later among the works it cites.
“Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions”
A.. Harrow and A.. Wei · 2020
Later among the works it cites.
“Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion”
Z. Chen, K. Liu and E. Vigoda · 2021
Later among the works it cites.
“Quantum Sub-Gaussian Mean Estimator”
Y. Hamoudi · 2021
Later among the works it cites.
“Reducing Isotropy and Volume to KLS: An O ∗ ( n 3 Ψ 2 ) O^{*}(n^{3}\Psi^{2}) Volume Algorithm”
H. Jia, A. Laddha, Y.. Lee and S. Vempala · 2021
Later among the works it cites.
“Simpler (Classical) and Faster (Quantum) Algorithms for Gibbs Partition Functions”
S. Arunachalam, V. Havlicek, G. Nannicini, K. Temme and P. Wocjan · 2022
Closest in time.
“Near-Optimal Quantum Algorithms for Multivariate Mean Estimation”
A. Cornelissen, Y. Hamoudi and S. Jerbi · 2022
Closest in time.