English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Quantum Max Cut (QMC) problem has emerged as a test-problem for designingapproximation algorithms for local Hamiltonian problems. In this paper weattack this problem using the algebraic structure of QMC, in particular therelationship between the quantum max cut Hamiltonian and the representationtheory of the symmetric group.  The first major contribution of this paper is an extension of non-commutativeSum of Squares (ncSoS) optimization techniques to give a new hierarchy ofrelaxations to Quantum Max Cut. The hierarchy we present is based onoptimizations over polynomials in the qubit swap operators. This is in contrastto the ``standard'' quantum Lasserre Hierarchy, which is based on polynomialsexpressed in terms of the Pauli matrices. To prove correctness of thishierarchy, we exploit a finite presentation of the algebra generated by thequbit swap operators. This presentation allows for the use of computeralgebraic techniques to manipulate simplify polynomials written in terms of theswap operators, and may be of independent interest. Surprisingly, we find thatlevel-2 of this new hierarchy is exact (up to tolerance $10^{-7}$) on all QMCinstances with uniform edge weights on graphs with at most 8 vertices.  The second major contribution of this paper is a polynomial-time algorithmthat exactly computes the maximum eigenvalue of the QMC Hamiltonian for certaingraphs, including graphs that can be "decomposed" as a signed combination ofcliques. A special case of the latter are complete bipartite graphs withuniform edge-weights, for which exact solutions are known from the work of Lieband Mattis. Our methods, which use representation theory of the symmetricgroup, can be seen as a generalization of the Lieb-Mattis result.

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