Quantum Max Cut for complete tripartite graphs

• URL: http://arxiv.org/abs/2512.03740v1
• Date: Wed, 03 Dec 2025 12:37:48 GMT
• Title: Quantum Max Cut for complete tripartite graphs
• Authors: Tea Štrekelj,
• Abstract summary: The Quantum Max-$d$-Cut ($d$-QMC) problem is a special instance of a $2$-local Hamiltonian problem.<n>This article solves the $d$-QMC problem for complete tripartite graphs for small local dimensions, $d le 3$.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Quantum Max-$d$-Cut ($d$-QMC) problem is a special instance of a $2$-local Hamiltonian problem, representing the quantum analog of the classical Max-$d$-Cut problem. The $d$-QMC problem seeks the largest eigenvalue of a Hamiltonian defined on a graph with $n$ vertices, where edges correspond to swap operators acting on $(\mathbb{C}^d)^{\otimes n}$. In recent years, progress has been made by investigating the algebraic structure of the $d$-QMC Hamiltonian. Building on this approach, this article solves the $d$-QMC problem for complete tripartite graphs for small local dimensions, $d \le 3$.

Related papers

• The $O(n\ o\infty)$ Rotor Model and the Quantum Spherical Model on Graphs [0.0]
  We show that the large $n$ limit of the $O(n)$ quantum rotor model defined on a general graph has the same critical behavior as the corresponding quantum spherical model.<n>We employ a classical to quantum mapping and use known results for the large $n$ limit of the classical $O(n)$ model on graphs.
  arXiv  Detail & Related papers  (2026-01-20T16:14:01Z)
• Hamiltonian Decoded Quantum Interferometry [69.7049555871155]
  We introduce Hamiltonian Decoded Quantum Interferometry (HDQI)<n>HDQI utilizes coherent measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian Bellians.<n>We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians.
  arXiv  Detail & Related papers  (2025-10-09T08:06:15Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• Quantum Max d-Cut via qudit swap operators [0.0]
  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.
  arXiv  Detail & Related papers  (2025-03-26T19:30:17Z)
• The classical limit of Quantum Max-Cut [0.16385815610837165]
  We show that the limit of large quantum spin $S$ should be understood as a semiclassical limit.<n>We present two families of classical approximation algorithms for $mathrmQMaxCut_S$ based on rounding the output of a semidefinite program to a product of Bloch coherent states.
  arXiv  Detail & Related papers  (2024-01-23T18:53:34Z)
• 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)
• Some Remarks on the Regularized Hamiltonian for Three Bosons with Contact Interactions [77.34726150561087]
  We discuss some properties of a model Hamiltonian for a system of three bosons interacting via zero-range forces in three dimensions. In particular, starting from a suitable quadratic form $Q$, the self-adjoint and bounded from below Hamiltonian $mathcal H$ can be constructed. We show that the threshold value $gamma_c$ is optimal, in the sense that the quadratic form $Q$ is unbounded from below if $gammagamma_c$.
  arXiv  Detail & Related papers  (2022-07-01T10:01:14Z)
• A New Look at the $C^{0}$-formulation of the Strong Cosmic Censorship Conjecture [68.8204255655161]
  We argue that for generic black hole parameters as initial conditions for Einstein equations, the metric is $C0$-extendable to a larger Lorentzian manifold. We prove it violates the "complexity=volume" conjecture for a low-temperature hyperbolic AdS$_d+1$ black hole dual to a CFT living on a ($d-1$)-dimensional hyperboloid $H_d-1$.
  arXiv  Detail & Related papers  (2022-06-17T12:14:33Z)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  We show how all properties of a quantum manifold of states are fully described by a gauge-invariant Bargmann. We show how our results have immediate applications to the modern theory of polarization.
  arXiv  Detail & Related papers  (2022-05-30T18:01:34Z)
• 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)
• Universality of the fully connected vertex in Laplacian continuous-time quantum walk problems [0.0]
  We prove that the continuous-time quantum walk (CTQW) -- with Hamiltonian $H=gamma L$ -- does not depend on the graph $G$. We apply our results to spatial search and quantum transport for single and multiple fully connected marked vertices.
  arXiv  Detail & Related papers  (2022-02-28T14:33:44Z)
• Solving Hamiltonian Cycle Problem using Quantum $\mathbb{Z}_2$ Lattice Gauge Theory [9.83302372715731]
  The Hamiltonian cycle (HC) problem in graph theory is a well-known NP-complete problem. We present an approach in terms of $mathbbZ$ lattice gauge theory defined on the lattice with the graph as its dual. For some random samples of small graphs, we demonstrate that the dependence of the average value of $g_c$ on $sqrtN_hc$, $N_hc$ being the number of HCs, and that of the average value of $frac1g_c$ on $N
  arXiv  Detail & Related papers  (2022-02-17T18:39:42Z)

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.