Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian
Problems
- URL: http://arxiv.org/abs/2012.12347v1
- Date: Tue, 22 Dec 2020 20:41:34 GMT
- Title: Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian
Problems
- Authors: Ojas Parekh and Kevin Thompson
- Abstract summary: k-Local Hamiltonian problem is a generalization of classical constraint satisfaction problems (k-CSP)
For strictly quadratic instances, which are maximally entangled instances, we provide a classical 0.764-time 0.764-approximation.
We conjecture these are the hardest instances to approximate.
Our work employs recently developed techniques for analyzing classical approximations of CSPs and is intended to be accessible to both quantum information scientists and classical computer scientists.
- Score: 3.553493344868414
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum k-Local Hamiltonian problem is a natural generalization of
classical constraint satisfaction problems (k-CSP) and is complete for QMA, a
quantum analog of NP. Although the complexity of k-Local Hamiltonian problems
has been well studied, only a handful of approximation results are known. For
Max 2-Local Hamiltonian where each term is a rank 3 projector, a natural
quantum generalization of classical Max 2-SAT, the best known approximation
algorithm was the trivial random assignment, yielding a 0.75-approximation. We
present the first approximation algorithm beating this bound, a classical
polynomial-time 0.764-approximation. For strictly quadratic instances, which
are maximally entangled instances, we provide a 0.801 approximation algorithm,
and numerically demonstrate that our algorithm is likely a 0.821-approximation.
We conjecture these are the hardest instances to approximate. We also give
improved approximations for quantum generalizations of other related classical
2-CSPs. Finally, we exploit quantum connections to a generalization of the
Grothendieck problem to obtain a classical constant-factor approximation for
the physically relevant special case of strictly quadratic traceless 2-Local
Hamiltonians on bipartite interaction graphs, where a inverse logarithmic
approximation was the best previously known (for general interaction graphs).
Our work employs recently developed techniques for analyzing classical
approximations of CSPs and is intended to be accessible to both quantum
information scientists and classical computer scientists.
Related papers
- When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input.
For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer.
For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
arXiv Detail & Related papers (2023-12-18T18:29:01Z) - Neural Time-Reversed Generalized Riccati Equation [60.92253836775246]
Hamiltonian equations offer an interpretation of optimality through auxiliary variables known as costates.
This paper introduces a novel neural-based approach to optimal control, with the aim of working forward-in-time.
arXiv Detail & Related papers (2023-12-14T19:29:37Z) - On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms [0.0]
A feature of constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard.
For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class.
We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be $E = N_mathrmunsat-N_mathrmsat$, spectrally filtered quantum optimization will return states with $E leq q_m.
arXiv Detail & Related papers (2023-12-11T04:15:55Z) - A quantum advantage over classical for local max cut [48.02822142773719]
Quantum optimization approximation algorithm (QAOA) has a computational advantage over comparable local classical techniques on degree-3 graphs.
Results hint that even small-scale quantum computation, which is relevant to the current state-of the art quantum hardware, could have significant advantages over comparably simple classical.
arXiv Detail & Related papers (2023-04-17T16:42:05Z) - Exponential quantum speedup in simulating coupled classical oscillators [1.9398245011675082]
We present a quantum algorithm for the classical dynamics of $2n$ coupled oscillators.
Our approach leverages a mapping between the Schr"odinger equation and Newton's equation for harmonic potentials.
We show that our approach solves a potentially practical application with an exponential speedup over classical computers.
arXiv Detail & Related papers (2023-03-23T03:24:03Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - An Improved Approximation Algorithm for Quantum Max-Cut [0.0]
We give an approximation algorithm for Quantum Max-Cut which works by rounding an SDP relaxation to an entangled quantum state.
For the EPR Hamiltonian, we give an approximation algorithm with approximation ratio $1 / sqrt2$ on all graphs.
arXiv Detail & Related papers (2022-09-06T15:45:04Z) - Average-case Speedup for Product Formulas [69.68937033275746]
Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems.
We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states.
Our results open doors to the study of quantum algorithms in the average case.
arXiv Detail & Related papers (2021-11-09T18:49:48Z) - On the complexity of quantum partition functions [2.6937287784482313]
We study the computational complexity of approximating quantities for $n$-qubit local Hamiltonians.
A classical algorithm with $mathrmpoly(n)$ approximates the free energy of a given $2$-local Hamiltonian.
arXiv Detail & Related papers (2021-10-29T00:05:25Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
We show how to apply the quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph.
We construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs.
arXiv Detail & Related papers (2020-11-26T18:22:21Z) - Quantum Assisted Eigensolver [0.0]
We propose a hybrid quantum-classical algorithm for approxing the ground state and ground state energy of a Hamiltonian.
The output from the quantum part of the algorithm is utilized as input for the classical computer.
arXiv Detail & Related papers (2020-09-23T08:33:18Z)
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.