The classical limit of Quantum Max-Cut
- URL: http://arxiv.org/abs/2401.12968v1
- Date: Tue, 23 Jan 2024 18:53:34 GMT
- Title: The classical limit of Quantum Max-Cut
- Authors: Vir B. Bulchandani, Stephen Piddock
- Abstract summary: We show that the limit of large quantum spin $S$ should be understood as a semiclassical limit.
We present two families of classical approximation algorithms for $mathrmQMaxCut_S$ based on rounding the output of a semidefinite program to a product of Bloch coherent states.
- Score: 0.18416014644193066
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: It is well-known in physics that the limit of large quantum spin $S$ should
be understood as a semiclassical limit. This raises the question of whether
such emergent classicality facilitates the approximation of computationally
hard quantum optimization problems, such as the local Hamiltonian problem. We
demonstrate this explicitly for spin-$S$ generalizations of Quantum Max-Cut
($\mathrm{QMaxCut}_S$), equivalent to the problem of finding the ground state
energy of an arbitrary spin-$S$ quantum Heisenberg antiferromagnet
($\mathrm{AFH}_S$). We prove that approximating the value of $\mathrm{AFH}_S$
to inverse polynomial accuracy is QMA-complete for all $S$, extending previous
results for $S=1/2$. We also present two distinct families of classical
approximation algorithms for $\mathrm{QMaxCut}_S$ based on rounding the output
of a semidefinite program to a product of Bloch coherent states. The
approximation ratios for both our proposed algorithms strictly increase with
$S$ and converge to the Bri\"et-Oliveira-Vallentin approximation ratio
$\alpha_{\mathrm{BOV}} \approx 0.956$ from below as $S \to \infty$.
Related papers
- Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
We present a quantum generalization of these tools through a generic bottleneck lemma.
This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles.
Even with sublinear barriers, we use Feynman-Kac techniques to lift classical to quantum ones establishing tight lower bound $T_mathrmmix = 2Omega(nalpha)$.
arXiv Detail & Related papers (2024-11-06T22:51:27Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature
and Bayesian Optimization [51.533164528799084]
We show that to estimate the normalizing constant within a small relative error, the level of difficulty depends on the value of $lambda$.
We find that this pattern holds true even when the function evaluations are noisy.
arXiv Detail & Related papers (2024-01-11T07:45:09Z) - Product states optimize quantum $p$-spin models for large $p$ [2.594420805049218]
We consider the problem of estimating the maximal energy of quantum $p$-local spin glass random Hamiltonians.
Our results challenge prevailing beliefs in physics that extremely low-temperature states of random local Hamiltonians should exhibit non-negligible entanglement.
arXiv Detail & Related papers (2023-09-21T01:10:50Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
We give a quantum approximation scheme for the classical $k$-means clustering problem in the QRAM model.
Our quantum algorithm runs in time $tildeO left( 2tildeO(frackvarepsilon) eta2 dright)$.
Unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines.
arXiv Detail & Related papers (2023-08-16T06:46:37Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - Quantum Speedups of Optimizing Approximately Convex Functions with
Applications to Logarithmic Regret Stochastic Convex Bandits [8.682187438614296]
A quantum algorithm finds an $x*incal K$ such that $F(x*)-min_xincal K F(x)leqepsilon$ using $tildeO(n3)$ quantum evaluation queries to $F$.
As an application, we give a quantum function algorithm for zeroth-order convex bandits with $tildeO(n5log2 T)$ regret, an exponential speedup in $T$ compared to the classical $
arXiv Detail & Related papers (2022-09-26T03:19:40Z) - The Quantum and Classical Streaming Complexity of Quantum and Classical
Max-Cut [0.07614628596146598]
We investigate the space complexity of two graph streaming problems: Max-Cut and its quantum analogue, Quantum Max-Cut.
Our work resolves the quantum and classical approximability of quantum and classical Max-Cut using $textrmo(n)$ space.
arXiv Detail & Related papers (2022-06-01T03:40:56Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation.
We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z) - Unique Games hardness of Quantum Max-Cut, and a conjectured
vector-valued Borell's inequality [6.621324975749854]
We show that the noise stability of a function $f:mathbbRn to -1, 1$ is the expected value of $f(boldsymbolx) cdot f(boldsymboly)$.
We conjecture that the expected value of $langle f(boldsymbolx), f(boldsymboly)rangle$ is minimized by the function $f(x) = x_leq k / Vert x_leq k /
arXiv Detail & Related papers (2021-11-01T20:45:42Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
arXiv Detail & Related papers (2020-08-24T06:50:57Z)
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.