An SU(2)-symmetric Semidefinite Programming Hierarchy for Quantum Max
Cut
- URL: http://arxiv.org/abs/2307.15688v2
- Date: Mon, 14 Aug 2023 15:16:09 GMT
- Title: An SU(2)-symmetric Semidefinite Programming Hierarchy for Quantum Max
Cut
- Authors: Jun Takahashi, Chaithanya Rayudu, Cunlu Zhou, Robbie King, Kevin
Thompson and Ojas Parekh
- Abstract summary: We introduce a family of semidefinite programming (SDP) relaxations based on the Navascues-Pironio-Acin hierarchy.
We show that the hierarchy converges to the optimal QMaxCut value at a finite level.
We numerically demonstrate that the SDP-solvability practically becomes an efficiently-computable generalization of frustration-freeness.
- Score: 0.6873984911061559
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Understanding and approximating extremal energy states of local Hamiltonians
is a central problem in quantum physics and complexity theory. Recent work has
focused on developing approximation algorithms for local Hamiltonians, and in
particular the ``Quantum Max Cut'' (QMax-Cut) problem, which is closely related
to the antiferromagnetic Heisenberg model. In this work, we introduce a family
of semidefinite programming (SDP) relaxations based on the
Navascues-Pironio-Acin (NPA) hierarchy which is tailored for QMaxCut by taking
into account its SU(2) symmetry. We show that the hierarchy converges to the
optimal QMaxCut value at a finite level, which is based on a new
characterization of the algebra of SWAP operators. We give several analytic
proofs and computational results showing exactness/inexactness of our hierarchy
at the lowest level on several important families of graphs.
We also discuss relationships between SDP approaches for QMaxCut and
frustration-freeness in condensed matter physics and numerically demonstrate
that the SDP-solvability practically becomes an efficiently-computable
generalization of frustration-freeness. Furthermore, by numerical demonstration
we show the potential of SDP algorithms to perform as an approximate method to
compute physical quantities and capture physical features of some
Heisenberg-type statistical mechanics models even away from the
frustration-free regions.
Related papers
- An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem.
We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
arXiv Detail & Related papers (2024-06-11T04:40:05Z) - Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation [39.20075231137991]
We address the computation of the cumulative distribution function (CDF) of the spectral measure of the Hamiltonian.
We introduce a signal processing technique for identifying the inflection point of the CDF.
We conduct numerical experiments on a 26-qubit fully-connected Heisenberg model using a truncated density-matrix renormalization group (DMRG) initial state of low bond dimension.
arXiv Detail & Related papers (2024-05-06T18:00:03Z) - Quantum Semidefinite Programming with Thermal Pure Quantum States [0.5639904484784125]
We show that a quantization'' of the matrix multiplicative-weight algorithm can provide approximate solutions to SDPs quadratically faster than the best classical algorithms.
We propose a modification of this quantum algorithm and show that a similar speedup can be obtained by replacing the Gibbs-state sampler with the preparation of thermal pure quantum (TPQ) states.
arXiv Detail & Related papers (2023-10-11T18:00:53Z) - Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions.
We develop an algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees.
arXiv Detail & Related papers (2023-09-19T22:53:17Z) - Efficient Approximation of Quantum Channel Fidelity Exploiting Symmetry [14.524074846672526]
We show that for a fixed output dimension of a quantum channel, we can compute the SDP in time with respect to the level of the hierarchy and input dimension.
As a consequence of our result, the optimal fidelity can be approximated with an accuracy of $epsilon$ in $mathrmpoly (1/epsilon, textinput dimension)$ time.
arXiv Detail & Related papers (2023-08-30T09:03:45Z) - Quantum Covariance Scalar Products and Efficient Estimation of Max-Ent
Projections [0.0]
The maximum-entropy principle (Max-Ent) is a valuable tool in statistical mechanics and quantum information theory.
It provides a method for inferring the state of a system by utilizing a reduced set of parameters associated with measurable quantities.
The computational cost of employing Max-Ent projections in simulations of quantum many-body systems is a significant drawback.
arXiv Detail & Related papers (2023-07-17T17:46:05Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
We provide a complete quantum circuit-level description of the algorithm from problem input to problem output.
We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
arXiv Detail & Related papers (2022-11-22T18:54:48Z) - Spectral Analysis of Product Formulas for Quantum Simulation [0.0]
We show that the Trotter step size needed to estimate an energy eigenvalue within precision can be improved in scaling from $epsilon$ to $epsilon1/2$ for a large class of systems.
Results partially generalize to diabatic processes, which remain in a narrow energy band separated from the rest of the spectrum by a gap.
arXiv Detail & Related papers (2021-02-25T03:17:25Z) - Variational Monte Carlo calculations of $\mathbf{A\leq 4}$ nuclei with
an artificial neural-network correlator ansatz [62.997667081978825]
We introduce a neural-network quantum state ansatz to model the ground-state wave function of light nuclei.
We compute the binding energies and point-nucleon densities of $Aleq 4$ nuclei as emerging from a leading-order pionless effective field theory Hamiltonian.
arXiv Detail & Related papers (2020-07-28T14:52:28Z) - Quantitative Propagation of Chaos for SGD in Wide Neural Networks [39.35545193410871]
In this paper, we investigate the limiting behavior of a continuous-time counterpart of the Gradient Descent (SGD)
We show 'propagation of chaos' for the particle system defined by this continuous-time dynamics under different scenarios.
We identify two under which different mean-field limits are obtained, one of them corresponding to an implicitly regularized version of the minimization problem at hand.
arXiv Detail & Related papers (2020-07-13T12:55:21Z)
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.