Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2402.14752

Limitations and Separations in the Quantum Sum-of-squares, and the Quantum Knapsack Problem

M. B. Hastings

Published Feb 22, 2024• 1 citation
arXivHTMLPDF

Abstract

We answer two questions regarding the sum-of-squares for the SYK model left open in Ref. 1, both of which are related to graphs. First (a "limitation"), we show that a fragment of the sum-of-squares, in which one considers commutation relations of degree-$4$ Majorana operators but does not impose any other relations on them, does not give the correct order of magnitude bound on the ground state energy. Second (a "separation"), we show that the graph invariant $Ψ(G)$ defined in Ref. 1 may be strictly larger than the independence number $α(G)$. The invariant $Ψ(G)$ is a bound on the norm of a Hamiltonian whose terms obey commutation relations determined by the graph $G$, and it was shown that $α(G)\leq Ψ(G) \leq \vartheta(G)$, where $\vartheta(\cdot)$ is the Lovasz theta function. We briefly discuss the case of $q\neq 4$ in the SYK model. Separately, we define a problem that we call the quantum knapsack problem.

DOI
10.48550/arxiv.2402.14752

Related papers

A Graph-Theoretic Approach to Quantum Measurement Incompatibility

Daniel McNulty

Measurement incompatibility--the impossibility of jointly measuring certain quantum observables--is a fundamental resource for quantum information processing. We develop a graph-theoretic framework for quantifying this resource for large families of binary measurements, including Pauli observables on multi-qubit systems and $k$-body Majorana observables on $n$-mode fermionic systems. To each set of observables we associate an anti-commutativity graph, whose vertices represent observables and whose edges indicate pairs that anti-commute. In this representation, the incompatibility robustness--the minimal amount of classical noise required to render the set jointly measurable--becomes a graph invariant. We derive general bounds on this invariant in terms of the Lovász number, clique number, and fractional chromatic number, and show that the Lovász number yields the correct asymptotic scaling for $k$-body Majorana observables. For line graphs $L(G)$, which naturally arise in the characterisation of exactly solvable spin models, we obtain spectral bounds on the robustness expressed through the energy and skew-energy of the underlying graph $G$. These bounds become tight for highly symmetric graphs, leading to closed formulas for several graph families. Finally, we identify structural conditions under which the robustness is determined by a simple function of the graph's maximum degree and the number of vertices and edges, and show that such extremal cases occur only when combinatorial structures such as Hadamard, conference or weighing matrices exist.

quant-pharXiv:2511.15954•Nov 21, 2025•0 citations

Perturbation Theory and the Sum of Squares

Matthew B. Hastings

The sum-of-squares (SoS) hierarchy is a powerful technique based on semi-definite programming that can be used for both classical and quantum optimization problems. This hierarchy goes under several names; in particular, in quantum chemistry it is called the reduced density matrix (RDM) method. We consider the ability of this hierarchy to reproduce weak coupling perturbation theory for three different kinds of systems: spin (or qubit) systems, bosonic systems (the anharmonic oscillator), and fermionic systems with quartic interactions. For such fermionic systems, we show that degree-$4$ SoS (called $2$-RDM in quantum chemsitry) does not reproduce second order perturbation theory but degree-$6$ SoS ($3$-RDM) does (and we conjecture that it reproduces third order perturbation theory). Indeed, we identify a fragment of degree-$6$ SoS which can do this, which may be useful for practical quantum chemical calculations as it may be possible to implement this fragment with less cost than the full degree-$6$ SoS. Remarkably, this fragment is very similar to one studied by Hastings and O'Donnell for the Sachdev-Ye-Kitaev (SYK) model.

arXiv:2205.12325•May 24, 2022•1 citation

Hypercontractivity, sum-of-squares proofs, and their applications

Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow +3 more

We study the computational complexity of approximating the 2-to-q norm of linear operators (defined as |A|2->q = maxv≠ 0|Av|q/|v|2) for q > 2, as well as connections between this question and issues arising in quantum information theory and the study of Khot's Unique Games Conjecture (UGC). We show the following: For any constant even integer q ≥ 4, a graph G is a small-set expander if and only if the projector into the span of the top eigenvectors of G's adjacency matrix has bounded 2->q norm. As a corollary, a good approximation to the 2->q norm will refute the Small-Set Expansion Conjecture --- a close variant of the UGC. We also show that such a good approximation can be obtained in exp(n2/q) time, thus obtaining a different proof of the known subexponential algorithm for Small-Set-Expansion. Constant rounds of the "Sum of Squares" semidefinite programing hierarchy certify an upper bound on the 2->4 norm of the projector to low degree polynomials over the Boolean cube, as well certify the unsatisfiability of the "noisy cube" and "short code" based instances of Unique-Games considered by prior works. This improves on the previous upper bound of exp(logO(1) n) rounds (for the "short code"), as well as separates the "Sum of Squares"/"Lasserre" hierarchy from weaker hierarchies that were known to require ω(1) rounds. We show reductions between computing the 2->4 norm and computing the injective tensor norm of a tensor, a problem with connections to quantum information theory. Three corollaries are: (i) the 2->4 norm is NP-hard to approximate to precision inverse-polynomial in the dimension, (ii) the 2->4 norm does not have a good approximation (in the sense above) unless 3-SAT can be solved in time exp(√n poly log(n)), and (iii) known algorithms for the quantum separability problem imply a non-trivial additive approximation for the 2->4 norm.

arXiv:1205.4484•ACM Symposium on Theory of Computing (STOC)•May 19, 2012•194 citations

Advantages and Limitations of Quantum Routing

Aniruddha Bapat, Andrew M. Childs, Alexey Vyacheslavovich Gorshkov +1 more

The Swap gate is a ubiquitous tool for moving information on quantum hardware, yet it can be considered a classical operation because it does not entangle product states. Genuinely quantum operations could outperform Swap for the task of permuting qubits within an architecture, which we call routing. We consider quantum routing in two models: (1) allowing arbitrary two-qubit unitaries, or (2) allowing Hamiltonians with norm-bounded interactions. We lower bound the circuit depth or time of quantum routing in terms of spectral properties of graphs representing the architecture interaction constraints, and give a generalized upper bound for all simple connected $n$-vertex graphs. In particular, we give conditions for a superpolynomial classical-quantum routing separation, which exclude graphs with a small spectral gap and graphs of bounded degree. Finally, we provide examples of a quadratic separation between gate-based and Hamiltonian routing models with a constant number of local ancillas per qubit and of an $Ω(n)$ speedup if we also allow fast local interactions.

arXiv:2206.01766•PRX Quantum•Feb 1, 2023•21 citations

Quantum Asymptotic Spectra of Graphs and Non-Commutative Graphs, and Quantum Shannon Capacities

Yinan Li, Jeroen Zuiddam

We study quantum versions of the Shannon capacity of graphs and non-commutative graphs. We introduce the asymptotic spectrum of graphs with respect to quantum and entanglement-assisted homomorphisms, and we introduce the asymptotic spectrum of non-commutative graphs with respect to entanglement-assisted homomorphisms. We apply Strassen's spectral theorem (J. Reine Angew. Math., 1988) in order to obtain dual characterizations of the corresponding Shannon capacities and asymptotic preorders in terms of their asymptotic spectra. This work extends the study of the asymptotic spectrum of graphs initiated by Zuiddam (Combinatorica, 2019) to the quantum domain. We then exhibit spectral points in the new quantum asymptotic spectra and discuss their relations with the asymptotic spectrum of graphs. In particular, we prove that the (fractional) real and complex Haemers bounds upper bound the quantum Shannon capacity, which is defined as the regularization of the quantum independence number (Mančinska and Roberson, J. Combin. Theory Ser. B, 2016), and that the fractional real and complex Haemers bounds are elements in the quantum asymptotic spectrum of graphs. This is in contrast to the Haemers bounds defined over certain finite fields, which can be strictly smaller than the quantum Shannon capacity. Moreover, since the Haemers bound can be strictly smaller than the Lovász theta function (Haemers, IEEE Trans. Inf. Theory, 1979), we find that the quantum Shannon capacity and the Lovász theta function do not coincide. As a consequence, two well-known conjectures in quantum information theory, namely: 1) the entanglement-assisted zero-error capacity of a classical channel is equal to the Lovász theta function and 2) maximally entangled states and projective measurements are sufficient to achieve the entanglement-assisted zero-error capacity, cannot both be true.

IEEE Transactions on Information Theory•Oct 22, 2020•6 citations

Spectral Certificates and Non-commutative Sum-of-Squares Lower Bounds for Hamiltonians

Nicholas Kocurek, Chinmay Nirkhe

A central question in quantum many-body physics is estimating the ground energy of a $k$-local Hamiltonian system. In this work, we present a spectral technique for certifying a lower bound on the ground energy of a random $n$-qubit Hamiltonian system defined as the sum of signed $k$-local Pauli operators. In particular, we prove that for any constant $\ell$, there exists an efficiently computable length $n^{O(\ell)}$ certificate that is always a lower bound on the ground energy with the promise that, with high probability over the random Hamiltonian distribution, the certificate value is an $\varepsilon$-good approximation of the true ground energy when the number of terms is sufficiently large. Second, we show by construction that this technique, while successful on average over random Hamiltonian systems, can fail to produce good certificates on worst-case instances. Our spectral technique for producing these certificates comes from extending classical results on $k$-XOR refutations to $k$-local Pauli Hamiltonians by crafting a quantum variant of the Kikuchi matrix for CSP refutations. To show the limitations of this technique, we prove non-commutative Sum-of-Squares lower bounds for worst-case signed $k$-local Pauli operators. More generally, we explore how the non-commutative Sum-of-Squares relaxation can be understood as augmenting the standard Sum-of-Squares relaxation with the commutation relations between the Pauli operators. We instantiate the resulting framework with a modification to prior quantum code-based NLTS Hamiltonians that yields stronger complexity guarantees for the low-energy space; our Hamiltonian family satisfies simultaneously (1) $Ω(\log n)$-circuit depth lower bounds for all low-energy states, (2) constant-gap NP-hardness to approximate the ground energy, and (3) a constant-gap non-commutative Sum-of-Squares integrality gap up to $Ω(n)$-levels.

cs.CCCross-listedarXiv:2511.02264•Nov 5, 2025•0 citations
We answer two questions regarding the sum-of-squares for the SYK model left open in Ref. 1, both of which are related to graphs. First (a "limitation"), we show that a fragment of the sum-of-squares, in which one considers commutation relations of degree-444 Majorana operators but does not impose any other relations on them, does not give the correct order of magnitude bound on the ground state energy. Second (a "separation"), we show that the graph invariant Ψ(G)Ψ(G)Ψ(G) defined in Ref. 1 may be strictly larger than the independence number α(G)α(G)α(G). The invariant Ψ(G)Ψ(G)Ψ(G) is a bound on the norm of a Hamiltonian whose terms obey commutation relations determined by the graph GGG, and it was shown that α(G)≤Ψ(G)≤ϑ(G)α(G)\leq Ψ(G) \leq \vartheta(G)α(G)≤Ψ(G)≤ϑ(G), where ϑ(⋅)\vartheta(\cdot)ϑ(⋅) is the Lovasz theta function. We briefly discuss the case of q≠4q\neq 4q=4 in the SYK model. Separately, we define a problem that we call the quantum knapsack problem.
Measurement incompatibility--the impossibility of jointly measuring certain quantum observables--is a fundamental resource for quantum information processing. We develop a graph-theoretic framework for quantifying this resource for large families of binary measurements, including Pauli observables on multi-qubit systems and kkk-body Majorana observables on nnn-mode fermionic systems. To each set of observables we associate an anti-commutativity graph, whose vertices represent observables and whose edges indicate pairs that anti-commute. In this representation, the incompatibility robustness--the minimal amount of classical noise required to render the set jointly measurable--becomes a graph invariant. We derive general bounds on this invariant in terms of the Lovász number, clique number, and fractional chromatic number, and show that the Lovász number yields the correct asymptotic scaling for kkk-body Majorana observables. For line graphs L(G)L(G)L(G), which naturally arise in the characterisation of exactly solvable spin models, we obtain spectral bounds on the robustness expressed through the energy and skew-energy of the underlying graph GGG. These bounds become tight for highly symmetric graphs, leading to closed formulas for several graph families. Finally, we identify structural conditions under which the robustness is determined by a simple function of the graph's maximum degree and the number of vertices and edges, and show that such extremal cases occur only when combinatorial structures such as Hadamard, conference or weighing matrices exist.
The sum-of-squares (SoS) hierarchy is a powerful technique based on semi-definite programming that can be used for both classical and quantum optimization problems. This hierarchy goes under several names; in particular, in quantum chemistry it is called the reduced density matrix (RDM) method. We consider the ability of this hierarchy to reproduce weak coupling perturbation theory for three different kinds of systems: spin (or qubit) systems, bosonic systems (the anharmonic oscillator), and fermionic systems with quartic interactions. For such fermionic systems, we show that degree-444 SoS (called 222-RDM in quantum chemsitry) does not reproduce second order perturbation theory but degree-666 SoS (333-RDM) does (and we conjecture that it reproduces third order perturbation theory). Indeed, we identify a fragment of degree-666 SoS which can do this, which may be useful for practical quantum chemical calculations as it may be possible to implement this fragment with less cost than the full degree-666 SoS. Remarkably, this fragment is very similar to one studied by Hastings and O'Donnell for the Sachdev-Ye-Kitaev (SYK) model.
We study the computational complexity of approximating the 2-to-q norm of linear operators (defined as |A|2->q = maxv≠ 0|Av|q/|v|2) for q > 2, as well as connections between this question and issues arising in quantum information theory and the study of Khot's Unique Games Conjecture (UGC). We show the following: For any constant even integer q ≥ 4, a graph G is a small-set expander if and only if the projector into the span of the top eigenvectors of G's adjacency matrix has bounded 2->q norm. As a corollary, a good approximation to the 2->q norm will refute the Small-Set Expansion Conjecture --- a close variant of the UGC. We also show that such a good approximation can be obtained in exp(n2/q) time, thus obtaining a different proof of the known subexponential algorithm for Small-Set-Expansion. Constant rounds of the "Sum of Squares" semidefinite programing hierarchy certify an upper bound on the 2->4 norm of the projector to low degree polynomials over the Boolean cube, as well certify the unsatisfiability of the "noisy cube" and "short code" based instances of Unique-Games considered by prior works. This improves on the previous upper bound of exp(logO(1) n) rounds (for the "short code"), as well as separates the "Sum of Squares"/"Lasserre" hierarchy from weaker hierarchies that were known to require ω(1) rounds. We show reductions between computing the 2->4 norm and computing the injective tensor norm of a tensor, a problem with connections to quantum information theory. Three corollaries are: (i) the 2->4 norm is NP-hard to approximate to precision inverse-polynomial in the dimension, (ii) the 2->4 norm does not have a good approximation (in the sense above) unless 3-SAT can be solved in time exp(√n poly log(n)), and (iii) known algorithms for the quantum separability problem imply a non-trivial additive approximation for the 2->4 norm.
The Swap gate is a ubiquitous tool for moving information on quantum hardware, yet it can be considered a classical operation because it does not entangle product states. Genuinely quantum operations could outperform Swap for the task of permuting qubits within an architecture, which we call routing. We consider quantum routing in two models: (1) allowing arbitrary two-qubit unitaries, or (2) allowing Hamiltonians with norm-bounded interactions. We lower bound the circuit depth or time of quantum routing in terms of spectral properties of graphs representing the architecture interaction constraints, and give a generalized upper bound for all simple connected nnn-vertex graphs. In particular, we give conditions for a superpolynomial classical-quantum routing separation, which exclude graphs with a small spectral gap and graphs of bounded degree. Finally, we provide examples of a quadratic separation between gate-based and Hamiltonian routing models with a constant number of local ancillas per qubit and of an Ω(n)Ω(n)Ω(n) speedup if we also allow fast local interactions.
We study quantum versions of the Shannon capacity of graphs and non-commutative graphs. We introduce the asymptotic spectrum of graphs with respect to quantum and entanglement-assisted homomorphisms, and we introduce the asymptotic spectrum of non-commutative graphs with respect to entanglement-assisted homomorphisms. We apply Strassen's spectral theorem (J. Reine Angew. Math., 1988) in order to obtain dual characterizations of the corresponding Shannon capacities and asymptotic preorders in terms of their asymptotic spectra. This work extends the study of the asymptotic spectrum of graphs initiated by Zuiddam (Combinatorica, 2019) to the quantum domain. We then exhibit spectral points in the new quantum asymptotic spectra and discuss their relations with the asymptotic spectrum of graphs. In particular, we prove that the (fractional) real and complex Haemers bounds upper bound the quantum Shannon capacity, which is defined as the regularization of the quantum independence number (Mančinska and Roberson, J. Combin. Theory Ser. B, 2016), and that the fractional real and complex Haemers bounds are elements in the quantum asymptotic spectrum of graphs. This is in contrast to the Haemers bounds defined over certain finite fields, which can be strictly smaller than the quantum Shannon capacity. Moreover, since the Haemers bound can be strictly smaller than the Lovász theta function (Haemers, IEEE Trans. Inf. Theory, 1979), we find that the quantum Shannon capacity and the Lovász theta function do not coincide. As a consequence, two well-known conjectures in quantum information theory, namely: 1) the entanglement-assisted zero-error capacity of a classical channel is equal to the Lovász theta function and 2) maximally entangled states and projective measurements are sufficient to achieve the entanglement-assisted zero-error capacity, cannot both be true.
A central question in quantum many-body physics is estimating the ground energy of a kkk-local Hamiltonian system. In this work, we present a spectral technique for certifying a lower bound on the ground energy of a random nnn-qubit Hamiltonian system defined as the sum of signed kkk-local Pauli operators. In particular, we prove that for any constant ℓ\ellℓ, there exists an efficiently computable length nO(ℓ)n^{O(\ell)}nO(ℓ) certificate that is always a lower bound on the ground energy with the promise that, with high probability over the random Hamiltonian distribution, the certificate value is an ε\varepsilonε-good approximation of the true ground energy when the number of terms is sufficiently large. Second, we show by construction that this technique, while successful on average over random Hamiltonian systems, can fail to produce good certificates on worst-case instances. Our spectral technique for producing these certificates comes from extending classical results on kkk-XOR refutations to kkk-local Pauli Hamiltonians by crafting a quantum variant of the Kikuchi matrix for CSP refutations. To show the limitations of this technique, we prove non-commutative Sum-of-Squares lower bounds for worst-case signed kkk-local Pauli operators. More generally, we explore how the non-commutative Sum-of-Squares relaxation can be understood as augmenting the standard Sum-of-Squares relaxation with the commutation relations between the Pauli operators. We instantiate the resulting framework with a modification to prior quantum code-based NLTS Hamiltonians that yields stronger complexity guarantees for the low-energy space; our Hamiltonian family satisfies simultaneously (1) Ω(log⁡n)Ω(\log n)Ω(logn)-circuit depth lower bounds for all low-energy states, (2) constant-gap NP-hardness to approximate the ground energy, and (3) a constant-gap non-commutative Sum-of-Squares integrality gap up to Ω(n)Ω(n)Ω(n)-levels.