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

• Efficient Pseudomode Representation and Complexity of Quantum Impurity Models [0.7373617024876725]
  Out-of-equilibrium fermionic quantum impurity models (QIM) describe a small interacting system coupled to a continuous fermionic bath. We find efficient bath representations as that of approximating a kernel of the bath's Feynman-Vernon influence functional by a sum of complex exponentials. To relate our findings to QIM, we derive an explicit Liouvillian that describes the time evolution of the combined impurity-pseudomodes system.
  arXiv  Detail & Related papers  (2024-09-13T13:31:53Z)
• 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)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• 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.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.