Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators

• URL: http://arxiv.org/abs/2307.15661v3
• Date: Wed, 24 Apr 2024 23:12:22 GMT
• Title: Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators
• Authors: Adam Bene Watts, Anirban Chowdhury, Aidan Epperly, J. William Helton, Igor Klep,
• Abstract summary: The Quantum Max Cut (QMC) problem has emerged as a test-problem for designing approximation algorithms for local Hamiltonian problems. In this paper we attack this problem using the algebraic structure of QMC, in particular the relationship between the quantum max cut Hamiltonian and the representation theory of the symmetric group.
• Score: 0.3177496877224142
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The Quantum Max Cut (QMC) problem has emerged as a test-problem for designing approximation algorithms for local Hamiltonian problems. In this paper we attack this problem using the algebraic structure of QMC, in particular the relationship between the quantum max cut Hamiltonian and the representation theory of the symmetric group. The first major contribution of this paper is an extension of non-commutative Sum of Squares (ncSoS) optimization techniques to give a new hierarchy of relaxations to Quantum Max Cut. The hierarchy we present is based on optimizations over polynomials in the qubit swap operators. This is in contrast to the "standard" quantum Lasserre Hierarchy, which is based on polynomials expressed in terms of the Pauli matrices. To prove correctness of this hierarchy, we exploit a finite presentation of the algebra generated by the qubit swap operators. This presentation allows for the use of computer algebraic techniques to manipulate and simplify polynomials written in terms of the swap operators, and may be of independent interest. Surprisingly, we find that level-2 of this new hierarchy is numerically exact (up to tolerance 10^(-7)) on all QMC instances with uniform edge weights on graphs with at most 8 vertices. The second major contribution of this paper is a polynomial-time algorithm that computes (in exact arithmetic) the maximum eigenvalue of the QMC Hamiltonian for certain graphs, including graphs that can be "decomposed" as a signed combination of cliques. A special case of the latter are complete bipartite graphs with uniform edge-weights, for which exact solutions are known from the work of Lieb and Mattis. Our methods, which use representation theory of the symmetric group, can be seen as a generalization of the Lieb-Mattis result.

Related papers

• Automorphism-Assisted Quantum Approximate Optimization Algorithm for efficient graph optimization [0.0]
  We use the Nauty package to identify graph automorphisms, focusing on determining edge equivalence classes. By exploiting these symmetries, we achieve a significant reduction in the complexity of the Hamiltonian. Our results show that using automorphism-based symmetries to reduce the Pauli terms in the Hamiltonian can significantly decrease computational overhead without compromising the quality of the solutions obtained.
  arXiv  Detail & Related papers  (2024-10-29T17:10:25Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• QuOp: A Quantum Operator Representation for Nodes [0.0]
  We derive an intuitive and novel method to represent nodes in a graph with quantum operators. This method does not require parameter training and is competitive with classical methods on scoring similarity between nodes.
  arXiv  Detail & Related papers  (2024-07-19T13:10:04Z)
• Quantum walk informed variational algorithm design [0.0]
  We present a theoretical framework for the analysis of amplitude transfer in Quantum Variational Algorithms (QVAs) We develop algorithms for unconstrained and constrained novel optimisations. We show significantly improved convergence over preexisting QVAs.
  arXiv  Detail & Related papers  (2024-06-17T15:04:26Z)
• Quantization of Large Language Models with an Overdetermined Basis [73.79368761182998]
  We introduce an algorithm for data quantization based on the principles of Kashin representation. Our findings demonstrate that Kashin Quantization achieves competitive or superior quality in model performance.
  arXiv  Detail & Related papers  (2024-04-15T12:38:46Z)
• Vectorization of the density matrix and quantum simulation of the von Neumann equation of time-dependent Hamiltonians [65.268245109828]
  We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations. We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix. A quantum algorithm to simulate the dynamics of the density matrix is proposed.
  arXiv  Detail & Related papers  (2023-06-14T23:08:51Z)
• The tilted CHSH games: an operator algebraic classification [77.34726150561087]
  This article introduces a general systematic procedure for solving any binary-input binary-output game. We then illustrate on the prominent class of tilted CHSH games. We derive for those an entire characterisation on the region exhibiting some quantum advantage.
  arXiv  Detail & Related papers  (2023-02-16T18:33:59Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Weighted slice rank and a minimax correspondence to Strassen's spectra [5.348876409230947]
  Strassen's spectra program characterizes optimal matrix algorithms through monotone functionals. Weighted slice rank encapsulates different notions of bipartiteness of quantum entanglement. New characterization can be extended to all fields.
  arXiv  Detail & Related papers  (2020-12-28T18:49:23Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• Approximate Graph Spectral Decomposition with the Variational Quantum Eigensolver [1.0152838128195465]
  Spectral graph theory studies the relationships between the eigenvectors and eigenvalues of Laplacian and adjacency matrices and their associated graphs. The Variational Quantum Eigensolver (VQE) algorithm was proposed as a hybrid quantum/classical algorithm. In this paper, we will expand upon the VQE algorithm to analyze the spectra of directed and undirected graphs.
  arXiv  Detail & Related papers  (2019-12-27T23:27:38Z)

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.