Quantum Max $d$-Cut via qudit swap operators

• URL: http://arxiv.org/abs/2503.20942v1
• Date: Wed, 26 Mar 2025 19:30:17 GMT
• Title: Quantum Max $d$-Cut via qudit swap operators
• Authors: Igor Klep, Tea Štrekelj, Jurij Volčič,
• Abstract summary: Quantum Max Cut (QMC) problem for systems of qubits is an example of a 2-local Hamiltonian problem.<n>This paper investigates the structure of a higher-dimensional analog of the QMC problem for systems of qudits.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Max Cut (QMC) problem for systems of qubits is an example of a 2-local Hamiltonian problem, and a prominent paradigm in computational complexity theory. This paper investigates the algebraic structure of a higher-dimensional analog of the QMC problem for systems of qudits. The Quantum Max d-Cut (d-QMC) problem asks for the largest eigenvalue of a Hamiltonian on a graph with n vertices whose edges correspond to swap operators acting on $(\mathbb{C}^d)^{\otimes n}$. The algebra generated by the swap operators is identified as a quotient of a free algebra modulo symmetric group relations and a single additional relation of degree d. This presentation leads to a tailored hierarchy of semidefinite programs, leveraging noncommutative polynomial optimization (NPO) methods, that converges to the solution of the d-QMC problem. For a large class of complete bipartite graphs, exact solutions for the d-QMC problem are derived using the representation theory of symmetric groups. This in particular includes the d-QMC problem for clique and star graphs on n vertices, for all d and n. Lastly, the paper addresses a refined d-QMC problem focused on finding the largest eigenvalue within each isotypic component (irreducible block) of the graph Hamiltonian. It is shown that the spectrum of the star graph Hamiltonian distinguishes between isotypic components of the 3-QMC problem. For general d, low-degree relations for separating isotypic components are presented, enabling adaptation of the global NPO hierarchy to efficiently compute the largest eigenvalue in each isotypic component.

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)
• The Complexity of Envy-Free Graph Cutting [44.58084909019557]
  We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, and every agent must be assigned a connected piece of this graph. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents and the number of edges in the graph.
  arXiv  Detail & Related papers  (2023-12-12T07:54:30Z)
• Quantum tomography of helicity states for general scattering processes [55.2480439325792]
  Quantum tomography has become an indispensable tool in order to compute the density matrix $rho$ of quantum systems in Physics. We present the theoretical framework for reconstructing the helicity quantum initial state of a general scattering process.
  arXiv  Detail & Related papers  (2023-10-16T21:23:42Z)
• New Approaches to Complexity via Quantum Graphs [0.0]
  We introduce and study the clique problem for quantum graphs.<n>Our approach utilizes a well-known connection between quantum graphs and quantum channels.<n>We show that, quantified over all channels, this problem is complete for QMA(2).<n>We also give a new proof of the celebrated reduction of QMA(k) to QMA(2).
  arXiv  Detail & Related papers  (2023-09-22T14:20:14Z)
• An SU(2)-symmetric Semidefinite Programming Hierarchy for Quantum Max Cut [0.6873984911061559]
  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.
  arXiv  Detail & Related papers  (2023-07-28T17:26:31Z)
• Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators [0.3177496877224142]
  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.
  arXiv  Detail & Related papers  (2023-07-28T16:45:16Z)
• Clique Homology is QMA1-hard [0.0]
  We show that the decision problem of determining homology groups of simplicial complexes is QMA1-hard. This suggests that the seemingly classical problem may in fact be quantum mechanical. We discuss potential implications for the problem of quantum advantage in topological data analysis.
  arXiv  Detail & Related papers  (2022-09-23T18:14:16Z)
• 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)
• Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
  We consider the complexity of the local Hamiltonian problem in the context of fermionic Hamiltonians with $mathcal N=2 $ supersymmetry. Our main motivation for studying this is the fact that the ground state energy of a supersymmetric system is exactly zero if and only if a certain cohomology group is nontrivial.
  arXiv  Detail & Related papers  (2021-06-30T18:00:01Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• 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)

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.