Related papers: An SU(2)-symmetric Semidefinite Programming Hierarchy for Quantum Max Cut

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

A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles. On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite Programming (SDP) approach. On ErdHos-R'enyi random graphs, the QGA demonstrates competitive performance, achieving median solutions within 92-96% of the SDP results.
arXiv Detail & Related papers (2025-01-02T05:06:16Z)
A Quantum Approximate Optimization Algorithm for Local Hamiltonian Problems [0.0]
Local Hamiltonian Problems (LHPs) are important problems that are computationally-complete and physically relevant for many-body quantum systems. We propose and analyze a quantum approximation which we call the Hamiltonian Quantum Approximate Optimization Algorithm (HamQAOA) Our results indicate that the linear-depth HamQAOA can deterministically prepare exact ground states of 1-dimensional antiferromagnetic Heisenberg spin chains.
arXiv Detail & Related papers (2024-12-12T12:22:08Z)
On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA [0.5999777817331315]
We investigate the Maximum Cut (MaxCut) problem on different graph classes with the Quantum Approximate Optimization Algorithm (QAOA) In particular, perturbations on the relationship between graph symmetries and the approximation ratio achieved by a QAOA simulation are considered. Through an analysis of the spectrum of the graphs and their perturbations, we aim to extract valuable insights into how symmetry impacts the performance of QAOA.
arXiv Detail & Related papers (2024-08-27T21:38:23Z)
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)
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)
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.