Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives

Anima Anandkumar; Iria W. Wang; Marco Pavone; Robin Brown; Susanne F. Yelin; Taylor L. Patti

arxiv: 2408.07774 · v3 · submitted 2024-08-14 · 🪐 quant-ph

Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives

Iria W. Wang , Robin Brown , Taylor L. Patti , Anima Anandkumar , Marco Pavone , Susanne F. Yelin This is my paper

Pith reviewed 2026-05-23 21:39 UTC · model grok-4.3

classification 🪐 quant-ph

keywords variational quantum algorithmssemidefinite programmingpolynomial optimizationproduct state encodingMax-kSATquantum relaxationnear-term quantum computing

0 comments

The pith

A product-register encoding upgrades variational quantum SDPs to solve polynomial optimization problems with linear resource growth.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents Product-State Lifting as a way to extend variational quantum semidefinite programs from quadratic to higher-degree polynomial objectives. This encoding uses additional product registers to represent higher powers, scaling resources linearly with degree k while keeping constraints independent of k. Readers should care because it provides a quantum approach to NP-hard polynomial problems like Max-kSAT without the size explosion of classical polynomial relaxations. The method pairs with existing vQSDP techniques such as the Hadamard test version to maintain near-term implementability. If successful, it creates a scalable path for quantum devices to tackle more complex optimization tasks directly.

Core claim

Product-State Lifting (PSL) is a simple product-register encoding that upgrades any vQSDP with basis-state encoding to tackle k-degree polynomial optimization. This requires only a linear increase in resources with constraints constant in k. When paired with the Hadamard-test vQSDP and approximate amplitude constraints, it enables approximation of problems such as Max-kSAT while preserving the device-friendly structure of vQSDPs.

What carries the argument

Product-State Lifting (PSL), the product-register encoding that represents polynomial monomials as tensor products of basis states on multiple registers.

If this is right

Polynomial degree becomes a linear parameter in resource requirements for vQSDPs.
No growth in the number of constraints as polynomial degree increases.
Direct application to Max-kSAT and other higher-order problems on near-term devices.
Maintains approximation guarantees from the underlying vQSDP method.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Could be combined with other variational quantum optimization techniques for broader use.
May reduce the need for classical post-processing in quantum optimization pipelines.
Small-scale implementations could test if error rates remain manageable with added registers.

Load-bearing premise

The product-state encoding integrates with existing vQSDP implementations like the Hadamard-test version without introducing dominant new error sources or variational difficulties.

What would settle it

An implementation on a small Max-3SAT instance where the lifted vQSDP either fails to converge or achieves an approximation ratio no better than a direct quadratic relaxation would indicate the claim does not hold.

Figures

Figures reproduced from arXiv: 2408.07774 by Anima Anandkumar, Iria W. Wang, Marco Pavone, Robin Brown, Susanne F. Yelin, Taylor L. Patti.

**Figure 2.** Figure 2: FIG. 2 [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Figure 3: FIG. 3 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

**Figure 4.** Figure 4: FIG. 4 [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗

read the original abstract

Many practically important NP-hard optimization problems are inherently higher-order polynomial optimizations, which are typically addressed using approximation algorithms. Classical relaxations express polynomial objectives over a polynomial basis and solve the resulting quadratic objective as a semidefinite program, which can significantly inflate problem size and degrade approximation behavior. Variational quantum analogues to classical semidefinite programs (vQSDPs) are near-term formulations geared towards quadratic objectives. We introduce Product-State Lifting (PSL), a simple product-register encoding that upgrades any vQSDP with basis-state encoding to tackle $k$-degree polynomial optimization. This upgrade requires only a linear increase in resources with constraints constant in $k$. As a worked example, we pair PSL with the recently-proposed vQSDP with the Hadamard test and approximate amplitude constraints [Quantum 7, 1057 (2023)], and outline an application to Max-$k$SAT. PSL maintains the device-friendly structure of vQSDPs while making polynomial degree a linear resource parameter, offering a general path from quadratic to polynomial optimization without the constraint growth typical of classical relaxations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

PSL gives a clean product-register lift that turns basis-state vQSDPs into polynomial solvers with linear qubit cost and k-independent constraints.

read the letter

The paper's main move is the Product-State Lifting construction. It encodes higher-degree polynomial objectives by adding product registers so that any existing basis-state vQSDP can be upgraded without the constraint count growing with degree k. Qubit overhead scales linearly instead. This directly targets the size inflation that classical SDP relaxations incur on polynomial problems. The worked example with the Hadamard-test vQSDP and Max-kSAT is a straightforward illustration of how the upgrade slots in. The resource scaling claim is internally consistent and does not rest on fitted parameters or self-reference. That part of the argument holds up on its own terms. The soft spot is that we see only the abstract and outline here. No full derivation, error bounds, or numerical runs are supplied, so it remains unclear whether the combined variational problem stays easy to optimize or whether approximation quality degrades in practice. Those are implementation questions rather than flaws in the encoding itself. The paper is aimed at people already working on variational quantum methods for combinatorial optimization. A reader who knows the prior vQSDP literature will immediately see what the lifting adds and where it fits. It is worth sending to peer review because the encoding idea is new relative to the cited work and solves a concrete scaling limitation without obvious circularity. The central claim about resource scaling is solid enough to merit referee attention even if later sections need tightening on the practical side.

Referee Report

2 major / 1 minor

Summary. The manuscript introduces Product-State Lifting (PSL), a product-register encoding that upgrades any basis-state vQSDP to k-degree polynomial objectives. The encoding requires only linear qubit overhead with the number of constraints independent of k. It is demonstrated as a worked example by pairing PSL with the Hadamard-test vQSDP (including approximate amplitude constraints) and outlining an application to Max-kSAT.

Significance. If the central encoding claim holds and can be combined with existing vQSDP implementations while preserving approximation behavior, PSL offers a device-friendly route to higher-order polynomial optimization on near-term hardware. This avoids the constraint blowup of classical polynomial SDP relaxations and makes polynomial degree a linear resource parameter rather than an exponential one.

major comments (2)

[§3] §3 (PSL construction): The claim that the lifted formulation exactly encodes the original k-degree objective relies on the product-state registers preserving the variational minimum; no explicit bound or derivation is supplied showing that the approximation ratio or optimality gap remains controlled for k>2.
[§4] §4 (Hadamard-test pairing): The outline does not analyze how the additional product registers affect the depth of the Hadamard-test circuit or the feasibility of the amplitude constraints, which is load-bearing for the assertion that the device-friendly structure is maintained without new dominant error sources.

minor comments (1)

[§3] Notation for the lifted operators and registers should be introduced with an explicit small-k example (e.g., k=3) to make the linear scaling concrete.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback. We address each major comment below with clarifications and commit to targeted revisions that strengthen the manuscript without altering its core claims.

read point-by-point responses

Referee: [§3] §3 (PSL construction): The claim that the lifted formulation exactly encodes the original k-degree objective relies on the product-state registers preserving the variational minimum; no explicit bound or derivation is supplied showing that the approximation ratio or optimality gap remains controlled for k>2.

Authors: The PSL encoding is constructed so that the expectation value of the lifted observable on the product-state registers is identically equal to the original k-degree polynomial evaluated on the corresponding basis states. Because the variational search remains over (lifted) basis states, the variational minimum of the lifted problem is exactly the same as that of the original problem for any k; the lifting introduces no additional optimality gap. The approximation ratio is therefore inherited unchanged from the underlying vQSDP solver. We will insert a short explicit derivation of this identity in the revised §3. revision: partial
Referee: [§4] §4 (Hadamard-test pairing): The outline does not analyze how the additional product registers affect the depth of the Hadamard-test circuit or the feasibility of the amplitude constraints, which is load-bearing for the assertion that the device-friendly structure is maintained without new dominant error sources.

Authors: We agree that a quantitative discussion of circuit depth and constraint feasibility is required. In the revision we will add an analysis showing that each additional product register increases Hadamard-test depth by a constant factor independent of k (owing to the product structure), while the approximate amplitude constraints remain separable across registers and therefore retain the same feasibility guarantees as in the base construction. This preserves the original error scaling. We will incorporate this discussion into the revised §4. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper introduces Product-State Lifting (PSL) as a new product-register encoding that upgrades existing vQSDP implementations for k-degree objectives with linear qubit overhead and constant constraints. No equations, fitted parameters, or self-citations are shown to reduce the central claim to a tautology or input by construction. The cited prior vQSDP work (Quantum 7, 1057) is external and the PSL construction is presented as an independent encoding choice whose resource scaling follows directly from the product-state definition without circular redefinition or renaming of known results. The derivation chain remains independent of the target polynomial optimization claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Based solely on the abstract, the central claim rests on the assumption that product-state registers can be integrated into existing vQSDP variational frameworks without altering their core approximation behavior or device compatibility.

axioms (1)

domain assumption Existing vQSDP methods with basis-state encoding can be extended via product registers while preserving their near-term implementability and approximation properties.
Invoked when the abstract states that PSL upgrades any vQSDP with basis-state encoding.

invented entities (1)

Product-State Lifting (PSL) no independent evidence
purpose: To encode k-degree polynomial terms using product registers so that vQSDPs can handle higher-order objectives.
New encoding introduced in the paper to achieve linear resource scaling.

pith-pipeline@v0.9.0 · 5736 in / 1353 out tokens · 53121 ms · 2026-05-23T21:39:03.403709+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

61 extracted references · 61 canonical work pages · 3 internal anchors

[1]

was recently proposed as a nearer-term and sample- efficient variational QSDP. HTAAC-QSDP can find ap- proximate solutions for problems with up to N ≤ 2n variables using only O(n) = O(log2 N) qubits, O(n) ex- pectation values, and O(poly(n)) classical calculations 1. This efficiency is largely furnished by estimating the ob- jective functions with the Had...

work page internal anchor Pith review Pith/arXiv arXiv 2024
[2]

or”, de- noted by ∨. These clauses are sometimes connected by the logi- cal “and

Max-2SAT In this section we consider a Max-2SAT instance on N − 1 boolean variables, whose values are represented as {xi}i∈{1,...,N −1}2. A Max-2SAT instance is a series of clauses written, without loss of generality, in Conjunc- tive Normal Form (CNF) 3. In CNF, a clause containing variables xi and xj is written as (xi ∨ xj), where either or both of xi a...

work page
[3]

feasible region

Semidefinite Programming (SDP) Semidefinite programming (SDP) and corresponding rounding procedures are standard techniques in classical optimization for bounding quadratic optimization prob- lems such as Max-2SAT. SDP is a class of convex optimization problems that aims to extremize a linear objective function over sym- metric positive semidefinite matri...

work page
[4]

(8), we re- place the matrix X with the density matrix ρ = |ψ⟩ ⟨ψ|, where |ψ⟩ = ψ0 ψ1

Evaluating the Objective Beginning with the SDP formulation in Eq. (8), we re- place the matrix X with the density matrix ρ = |ψ⟩ ⟨ψ|, where |ψ⟩ = ψ0 ψ1 ... ψ 2n−1 T in the computational basis. In particular, ψi corresponds to yi for all i ∈ {0, 1, ..., N − 1}, where we recall N ≤ 2n. The elements ρi,j of ρ represent yiyj, such that the quantum equivalent...

work page
[5]

population-balancing

Approximate Amplitude Constraints For Max-2SAT we wish to approximately enforce the constraint ρi,i = 2−n from Eq. (9). We note that enforc- ing ρi,i = 2−n is equivalent to enforcing |ψ0|2 = |ψ1|2 = ... = |ψ2n−1|2 up to normalization. This yields 2 n − 1 degrees of freedom, defined by 2 n − 1 unique equations 5. We can rewrite this set of 2 n − 1 equation...

work page
[6]

The loss func- tion is given by L = ⟨σz anc.⟩W − + λ   X ⟨σ,ρ⟩∈P ⟨σ, ρ⟩ + ⟨σz anc.⟩P  

The Loss Function All three elements – the objective function, population- balancing unitary, and Pauli strings – may be combined as a single loss function to be minimized. The loss func- tion is given by L = ⟨σz anc.⟩W − + λ   X ⟨σ,ρ⟩∈P ⟨σ, ρ⟩ + ⟨σz anc.⟩P   . (17) The first term ⟨σz anc.⟩W − results from the Hadamard test used to estimate the object...

work page
[7]

One method uses sample-efficent estimation (SEE) and yields an un-rounded solution

Retrieving Solutions Once the loss is minimized, there are two ways to re- trieve solutions from the resulting quantum state. One method uses sample-efficent estimation (SEE) and yields an un-rounded solution. Another method requires full state tomography (FST), but its complexity does not depend on the degree of the polynomial and the result mimics class...

work page
[8]

The Polynomial Optimization Problem In Max-3SAT, clauses are written in the form ( xi ∨ xj ∨ xk), where any of xi, xj, and xk may be replaced by their negations. By incorporating y0 analogously to Max-2SAT, the truth value of the clause (xi ∨ xj ∨ xk) is expressed as v(xi ∨ xj ∨ xk) = 1 − v(¬xi)v(¬xj)v(¬xk) = 1 + y0yi 8 + 1 + y0yj 8 + 1 + y0yk 8 + 1 − yiy...

work page
[9]

polynomial basis

Sum-of-Squares (SOS) SOS programming is a core discipline in operations re- search [30]. In this section, we provide a cursory overview of the relevant SOS formulae, providing a more detailed treatment in the Appendix. SOS programming determines whether a degree-2 D polynomial function F (y), where y = {yi}i∈{0,1,...,N −1}, can be factored as a sum of squ...

work page
[10]

multiple register

Evaluating the Objective The polynomial objective function for Max-3SAT (Eq. (22)) may be rewritten as X ℓ v(Cℓ) = X i>j>q>l W +,(1) i,j + W +,(2) ij,ql − yiyjW −,(1) i,j + yiyjyqylW −,(2) ij,ql (25) where W +,(1) i,j = a(1) i,j + b(1) i,j , W −,(1) i,j = a(1) i,j − b(1) i,j , W +,(2) ij,ql = a(2) ij,ql + b(2) ij,ql, and W −,(2) ij,ql = a(2) ij,ql − b(2) ...

work page
[11]

In Section II C 2, we describe how we may approx- imately enforce this constraint using O(n2) Pauli strings and a population-balancing unitary

Approximate Amplitude Constraints We want to enforce the constraint ρi,i = 2 −n for all i ≤ N. In Section II C 2, we describe how we may approx- imately enforce this constraint using O(n2) Pauli strings and a population-balancing unitary. Since we encode the objective function using product states, we do not re- quire any additional constraints. Specifica...

work page
[12]

(28) 2n−1 ⟨0|⊗n H ⊗nW +,(1)H ⊗n |0⟩⊗n + 22n−1 ⟨0|⊗2n H ⊗2nW +,(2)H ⊗2n |0⟩⊗2n + 2n−1 ⟨Ψ(1)| W −,(1) |Ψ(1)⟩ + 22n−1 ⟨Ψ(2)| W −,(2) |Ψ(2)⟩

Retrieving Solutions Extending the SEE method in Section II C 4, we eval- uate the un-rounded solution using the quantum analog of Eq. (28) 2n−1 ⟨0|⊗n H ⊗nW +,(1)H ⊗n |0⟩⊗n + 22n−1 ⟨0|⊗2n H ⊗2nW +,(2)H ⊗2n |0⟩⊗2n + 2n−1 ⟨Ψ(1)| W −,(1) |Ψ(1)⟩ + 22n−1 ⟨Ψ(2)| W −,(2) |Ψ(2)⟩ . (35) The first term is estimated using a Hadamard test with unitary UW +,(1) acting...

work page
[13]

SOS vs. HTAAC-QSOS To test the performance of HTAAC-QSOS against SOS, we generate several Max-3SAT instances by draw- ing variables from a uniform distribution and removing clauses with repeating variables. The SOS techniques

work page
[14]

We choose problems with 20 variables each because they may be approximated by SOS within reasonable time

are used to obtain classical solutions. We choose problems with 20 variables each because they may be approximated by SOS within reasonable time. We remark that SOS often yields very tight upper bounds, frequently finding the optimal solution [9, 38]. However, since these upper bounds do not necessarily correspond to feasible solutions, we use a rounding ...

work page
[15]

HTAAC-QSOS To gauge the performance of HTAAC-QSOS for larger problems, we draw instances with 70 to 110 variables from the 2016 MaxSAT evaluation [26]

Classical Heuristic vs. HTAAC-QSOS To gauge the performance of HTAAC-QSOS for larger problems, we draw instances with 70 to 110 variables from the 2016 MaxSAT evaluation [26]. Since classical SOS is intractable for larger problems, the best known so- lutions are given by the winning heuristic solutions from the MaxSAT evaluation. These solvers primarily l...

work page 2016
[16]

multiple register

Evaluating the Objective Max-kSAT can be expressed as a degree-2 D polyno- mial optimization problem, where 2 D = 2 ceil( k/2) is the maximum degree of the polynomial objective 6. The 6 We remind the reader that Max- kSAT can also be expressed as a degree- k polynomial optimization problem, but we introduce 11 Max-3SAT Instance HTAAC-QSOS (SEE) HTAAC-QSOS...

work page
[17]

Thus, the number of mea- surements required to approximately enforce constraints is independent of k

Approximate Amplitude Constraints The Pauli strings and the population-balancing uni- tary are formulated identically to those in Max-3SAT (see Section III A 2), since the equality constraint in the opti- mization problem is the same. Thus, the number of mea- surements required to approximately enforce constraints is independent of k

work page
[18]

(36) can be generalized to DX d=1 2nd−1 α ⟨σz anc.⟩⊗H W +,(d) − ⟨σz anc.⟩W −,(d) , (40) where we recall D = ceil( k/2) and each term may be evaluated with a Hadamard test

Retrieving Solutions The un-rounded SEE solution for Max-3SAT in Eq. (36) can be generalized to DX d=1 2nd−1 α ⟨σz anc.⟩⊗H W +,(d) − ⟨σz anc.⟩W −,(d) , (40) where we recall D = ceil( k/2) and each term may be evaluated with a Hadamard test. We therefore require O(k) = O(D) Hadamard tests to determine this un- rounded solution. The second rounding method f...

work page
[19]

T. L. Patti, J. Kossaifi, A. Anandkumar, and S. F. Yelin, Quantum goemans-williamson algorithm with the hadamard test and approximate amplitude constraints, Quantum 7, 1057 (2023)

work page 2023
[20]

Biamonte, P

J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum machine learning, Na- ture 549, 195–202 (2017)

work page 2017
[21]

Y. Cao, J. Romero, J. P. Olson, M. Degroote, P. D. John- son, M. Kieferov´ a, I. D. Kivlichan, T. Menke, B. Per- opadre, N. P. D. Sawaya, S. Sim, L. Veis, and A. Aspuru- Guzik, Quantum chemistry in the age of quantum com- puting, Chemical Reviews 119, 10856–10915 (2019)

work page 2019
[22]

Montanaro, Quantum algorithms: an overview, npj Quantum Information 2, 1–8 (2016)

A. Montanaro, Quantum algorithms: an overview, npj Quantum Information 2, 1–8 (2016)

work page 2016
[23]

Preskill, Quantum computing in the nisq era and be- yond, Quantum 2, 79 (2018)

J. Preskill, Quantum computing in the nisq era and be- yond, Quantum 2, 79 (2018)

work page 2018
[24]

Korte and J

B. Korte and J. Vygen, Introduction, in Combinatorial Optimization: Theory and Algorithms (Springer, Berlin, Heidelberg, 2018) p. 1–13

work page 2018
[25]

J. Berg, A. Hyttinen, and M. J¨ arvisalo, Applications of maxsat in data analysis, in EPiC Series in Computing , Vol. 59 (EasyChair, 2019) p. 50–64

work page 2019
[26]

Vandenberghe and S

L. Vandenberghe and S. Boyd, Semidefinite program- ming, SIAM Review 38, 49–95 (1996). 13

work page 1996
[27]

V. V. Vazirani, Approximation Algorithms (Springer Link, 2001)

work page 2001
[28]

F. G. S. L. Brand˜ ao, R. Kueng, and D. S. Fran¸ ca, Faster quantum and classical sdp approximations for quadratic binary optimization, Quantum 6, 625 (2022)

work page 2022
[29]

F. G. Brandao and K. M. Svore, Quantum speed-ups for solving semidefinite programs, in 2017 IEEE 58th An- nual Symposium on Foundations of Computer Science (FOCS) (2017) p. 415–426

work page 2017
[30]

J. v. Apeldoorn, A. Gily´ en, S. Gribling, and R. d. Wolf, Quantum sdp-solvers: Better upper and lower bounds, Quantum 4, 230 (2020)

work page 2020
[31]

van Apeldoorn and A

J. van Apeldoorn and A. Gily´ en, Improvements in quantum sdp-solving with applications, in DROPS- IDN/v2/document/10.4230/LIPIcs.ICALP.2019.99 (Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2019)

work page doi:10.4230/lipics.icalp.2019.99 2019
[32]

Ebadi, A

S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuleti´ c, and M. D. Lukin, Quantum optimization of maximum independent set using rydberg atom arrays, Science ...

work page 2022
[33]

F. G. S. L. Brand˜ ao, A. Kalev, T. Li, C. Y.- Y. Lin, K. M. Svore, and X. Wu, Quantum sdp solvers: Large speed-ups, optimality, and applications to quantum learning, in DROPS- IDN/v2/document/10.4230/LIPIcs.ICALP.2019.27 (Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2019)

work page doi:10.4230/lipics.icalp.2019.27 2019
[34]

Patel, P

D. Patel, P. J. Coles, and M. M. Wilde, Vari- ational quantum algorithms for semidefinite pro- gramming, arXiv 10.48550/arXiv.2112.08859 (2021), arXiv:2112.08859 [quant-ph]

work page doi:10.48550/arxiv.2112.08859 2021
[35]

Albash and D

T. Albash and D. A. Lidar, Adiabatic quantum compu- tation, Reviews of Modern Physics 90, 015002 (2018)

work page 2018
[36]

A Quantum Approximate Optimization Algorithm

E. Farhi, J. Goldstone, and S. Gutmann, A quan- tum approximate optimization algorithm, arXiv 10.48550/arXiv.1411.4028 (2014)

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1411.4028 2014
[37]

Quantum Computation by Adiabatic Evolution

E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution, arXiv 10.48550/arXiv.quant-ph/0001106 (2000)

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.quant-ph/0001106 2000
[38]

Gibney, D-wave upgrade: How scientists are using the world’s most controversial quantum computer, Na- ture 541, 447–448 (2017)

E. Gibney, D-wave upgrade: How scientists are using the world’s most controversial quantum computer, Na- ture 541, 447–448 (2017)

work page 2017
[39]

Kadowaki and H

T. Kadowaki and H. Nishimori, Quantum annealing in the transverse ising model, Physical Review E 58, 5355–5363 (1998)

work page 1998
[40]

J. M. Arrazola, V. Bergholm, K. Br´ adler, T. R. Brom- ley, M. J. Collins, I. Dhand, A. Fumagalli, T. Gerrits, A. Goussev, L. G. Helt, J. Hundal, T. Isacsson, R. B. Israel, J. Izaac, S. Jahangiri, R. Janik, N. Killoran, S. P. Kumar, J. Lavoie, A. E. Lita, D. H. Mahler, M. Menotti, B. Morrison, S. W. Nam, L. Neuhaus, H. Y. Qi, N. Que- sada, A. Repingon, K....

work page 2021
[41]

Cerezo, A

M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Variational quantum algo- rithms, Nature Reviews Physics 3, 625–644 (2021)

work page 2021
[42]

Bittel and M

L. Bittel and M. Kliesch, Training variational quan- tum algorithms is np-hard, Physical Review Letters 127, 120502 (2021)

work page 2021
[43]

Cai and X

S. Cai and X. Zhang, Pure maxsat and its applications to combinatorial optimization via linear local search, in Principles and Practice of Constraint Programming , edited by H. Simonis (Springer International Publishing, Cham, 2020) p. 90–106

work page 2020
[44]

of the 19th International Conference on Theory and A

O. of the 19th International Conference on Theory and A. of Satisfiability Testing, The homepage of eighth max-sat evaluation, http://maxsat.ia.udl.cat/ introduction/ (2016)

work page 2016
[45]

P. A. Parrilo, Semidefinite programming relaxations for semialgebraic problems, Mathematical Programming 96, 293–320 (2003)

work page 2003
[46]

M. X. Goemans and D. P. Williamson, Improved approx- imation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM 42, 1115–1145 (1995)

work page 1995
[47]

Hickey and F

R. Hickey and F. Bacchus, Large neighbourhood search for anytime maxsat solving, in Proceedings of the Thirty- First International Joint Conference on Artificial Intel- ligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022 , edited by L. D. Raedt (ijcai.org, 2022) pp. 1818–1824

work page 2022
[48]

A. A. Ahmadi, Sum of squares (sos) techniques: An in- troduction

work page
[49]

Prajna, A

S. Prajna, A. Papachristodoulou, and P. Parrilo, Intro- ducing sostools: a general purpose sum of squares pro- gramming solver, in Proceedings of the 41st IEEE Con- ference on Decision and Control, 2002. , Vol. 1 (2002) p. 741–746 vol.1

work page 2002
[50]

Harrach, Solving an inverse elliptic coefficient prob- lem by convex non-linear semidefinite programming, Op- timization Letters 16, 1599–1609 (2022)

B. Harrach, Solving an inverse elliptic coefficient prob- lem by convex non-linear semidefinite programming, Op- timization Letters 16, 1599–1609 (2022)

work page 2022
[51]

A. Gepp, G. Harris, and B. Vanstone, Financial applica- tions of semidefinite programming: a review and call for interdisciplinary research, Accounting and Finance 60, 3527–3555 (2020)

work page 2020
[52]

S. A. Cook, The complexity of theorem-proving proce- dures, in Proceedings of the third annual ACM sympo- sium on Theory of computing , STOC ’71 (Association for Computing Machinery, New York, NY, USA, 1971) p. 151–158

work page 1971
[53]

Howson, Logic with Trees: An Introduction to Sym- bolic Logic (Routledge, New York, 1997)

C. Howson, Logic with Trees: An Introduction to Sym- bolic Logic (Routledge, New York, 1997)

work page 1997
[54]

Lemon, A

A. Lemon, A. M.-C. So, and Y. Ye, Low-rank semidef- inite programming: Theory and applications, Founda- tions and Trends in Optimization 2, 1–156 (2016)

work page 2016
[55]

Hakemi, M

S. Hakemi, M. Houshmand, E. KheirKhah, and S. A. Hosseini, A review of recent advances in quantum- inspired metaheuristics, Evolutionary Intelligence 17, 627–642 (2024)

work page 2024
[56]

van Maaren, L

H. van Maaren, L. van Norden, and M. J. H. Heule, Sums of squares based approximation algorithms for max-sat, Discrete Applied Mathematics 156, 1754–1779 (2008)

work page 2008
[57]

M. B. Hastings, Perturbation theory and the sum of squares, arXiv (2024), arXiv:2205.12325 [cond-mat, physics:hep-th, physics:quant-ph]

work page arXiv 2024
[58]

A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri, Com- plete family of separability criteria, Physical Review A 69, 022308 (2004). 14 Appendix A: Sum-of-Squares (SOS) and Rounding Procedures In this section of the appendix, we provide more de- tails on the sum-of-squares (SOS) method as well as its rounding procedures

work page 2004
[59]

Let F (y) be a multivariate polynomial, where y de- notes the N variables {yi}i∈{0,1,...,N −1}

SOS Hierarchy While there exist several relaxation algorithms and rounding procedures used to approximate solutions to Max-kSAT and similar problems, we choose SOS as the most standard and systematic method as a classical benchmark for our algorithm. Let F (y) be a multivariate polynomial, where y de- notes the N variables {yi}i∈{0,1,...,N −1}. The goal o...

work page
[60]

In this way, the problem becomes the SDP maximize Q ∈ S+ ⟨W, Q⟩ subject to bbT , Q = F (y) (A9) where W is defined such that ⟨W, Q⟩ ∝ γ

Specifically, we define b ≡ 1 y0 y1 y2 y3 y0y1 y2y3 T (A8) and determine Q as a function of γ and the coefficients of ti(y) such that F (y) is SOS, that is, F (y) = bT Qb = bbT , QT . In this way, the problem becomes the SDP maximize Q ∈ S+ ⟨W, Q⟩ subject to bbT , Q = F (y) (A9) where W is defined such that ⟨W, Q⟩ ∝ γ. Solving the SDP, we obtain an upper ...

work page
[61]

[38], and the steps are as follows

Rounding Procedures The rounding procedure used in our SOS solution is equivalent one of the rounding procedures described by van Maaren et al. [38], and the steps are as follows. It can be shown that the optimal solution Q of the SOS method described in the previous section has an eigen- value zero. We determine the orthogonal basis of eigen- vectors v1,...

work page

[1] [1]

was recently proposed as a nearer-term and sample- efficient variational QSDP. HTAAC-QSDP can find ap- proximate solutions for problems with up to N ≤ 2n variables using only O(n) = O(log2 N) qubits, O(n) ex- pectation values, and O(poly(n)) classical calculations 1. This efficiency is largely furnished by estimating the ob- jective functions with the Had...

work page internal anchor Pith review Pith/arXiv arXiv 2024

[2] [2]

or”, de- noted by ∨. These clauses are sometimes connected by the logi- cal “and

Max-2SAT In this section we consider a Max-2SAT instance on N − 1 boolean variables, whose values are represented as {xi}i∈{1,...,N −1}2. A Max-2SAT instance is a series of clauses written, without loss of generality, in Conjunc- tive Normal Form (CNF) 3. In CNF, a clause containing variables xi and xj is written as (xi ∨ xj), where either or both of xi a...

work page

[3] [3]

feasible region

Semidefinite Programming (SDP) Semidefinite programming (SDP) and corresponding rounding procedures are standard techniques in classical optimization for bounding quadratic optimization prob- lems such as Max-2SAT. SDP is a class of convex optimization problems that aims to extremize a linear objective function over sym- metric positive semidefinite matri...

work page

[4] [4]

(8), we re- place the matrix X with the density matrix ρ = |ψ⟩ ⟨ψ|, where |ψ⟩ = ψ0 ψ1

Evaluating the Objective Beginning with the SDP formulation in Eq. (8), we re- place the matrix X with the density matrix ρ = |ψ⟩ ⟨ψ|, where |ψ⟩ = ψ0 ψ1 ... ψ 2n−1 T in the computational basis. In particular, ψi corresponds to yi for all i ∈ {0, 1, ..., N − 1}, where we recall N ≤ 2n. The elements ρi,j of ρ represent yiyj, such that the quantum equivalent...

work page

[5] [5]

population-balancing

Approximate Amplitude Constraints For Max-2SAT we wish to approximately enforce the constraint ρi,i = 2−n from Eq. (9). We note that enforc- ing ρi,i = 2−n is equivalent to enforcing |ψ0|2 = |ψ1|2 = ... = |ψ2n−1|2 up to normalization. This yields 2 n − 1 degrees of freedom, defined by 2 n − 1 unique equations 5. We can rewrite this set of 2 n − 1 equation...

work page

[6] [6]

The loss func- tion is given by L = ⟨σz anc.⟩W − + λ   X ⟨σ,ρ⟩∈P ⟨σ, ρ⟩ + ⟨σz anc.⟩P  

The Loss Function All three elements – the objective function, population- balancing unitary, and Pauli strings – may be combined as a single loss function to be minimized. The loss func- tion is given by L = ⟨σz anc.⟩W − + λ   X ⟨σ,ρ⟩∈P ⟨σ, ρ⟩ + ⟨σz anc.⟩P   . (17) The first term ⟨σz anc.⟩W − results from the Hadamard test used to estimate the object...

work page

[7] [7]

One method uses sample-efficent estimation (SEE) and yields an un-rounded solution

Retrieving Solutions Once the loss is minimized, there are two ways to re- trieve solutions from the resulting quantum state. One method uses sample-efficent estimation (SEE) and yields an un-rounded solution. Another method requires full state tomography (FST), but its complexity does not depend on the degree of the polynomial and the result mimics class...

work page

[8] [8]

The Polynomial Optimization Problem In Max-3SAT, clauses are written in the form ( xi ∨ xj ∨ xk), where any of xi, xj, and xk may be replaced by their negations. By incorporating y0 analogously to Max-2SAT, the truth value of the clause (xi ∨ xj ∨ xk) is expressed as v(xi ∨ xj ∨ xk) = 1 − v(¬xi)v(¬xj)v(¬xk) = 1 + y0yi 8 + 1 + y0yj 8 + 1 + y0yk 8 + 1 − yiy...

work page

[9] [9]

polynomial basis

Sum-of-Squares (SOS) SOS programming is a core discipline in operations re- search [30]. In this section, we provide a cursory overview of the relevant SOS formulae, providing a more detailed treatment in the Appendix. SOS programming determines whether a degree-2 D polynomial function F (y), where y = {yi}i∈{0,1,...,N −1}, can be factored as a sum of squ...

work page

[10] [10]

multiple register

Evaluating the Objective The polynomial objective function for Max-3SAT (Eq. (22)) may be rewritten as X ℓ v(Cℓ) = X i>j>q>l W +,(1) i,j + W +,(2) ij,ql − yiyjW −,(1) i,j + yiyjyqylW −,(2) ij,ql (25) where W +,(1) i,j = a(1) i,j + b(1) i,j , W −,(1) i,j = a(1) i,j − b(1) i,j , W +,(2) ij,ql = a(2) ij,ql + b(2) ij,ql, and W −,(2) ij,ql = a(2) ij,ql − b(2) ...

work page

[11] [11]

In Section II C 2, we describe how we may approx- imately enforce this constraint using O(n2) Pauli strings and a population-balancing unitary

Approximate Amplitude Constraints We want to enforce the constraint ρi,i = 2 −n for all i ≤ N. In Section II C 2, we describe how we may approx- imately enforce this constraint using O(n2) Pauli strings and a population-balancing unitary. Since we encode the objective function using product states, we do not re- quire any additional constraints. Specifica...

work page

[12] [12]

(28) 2n−1 ⟨0|⊗n H ⊗nW +,(1)H ⊗n |0⟩⊗n + 22n−1 ⟨0|⊗2n H ⊗2nW +,(2)H ⊗2n |0⟩⊗2n + 2n−1 ⟨Ψ(1)| W −,(1) |Ψ(1)⟩ + 22n−1 ⟨Ψ(2)| W −,(2) |Ψ(2)⟩

Retrieving Solutions Extending the SEE method in Section II C 4, we eval- uate the un-rounded solution using the quantum analog of Eq. (28) 2n−1 ⟨0|⊗n H ⊗nW +,(1)H ⊗n |0⟩⊗n + 22n−1 ⟨0|⊗2n H ⊗2nW +,(2)H ⊗2n |0⟩⊗2n + 2n−1 ⟨Ψ(1)| W −,(1) |Ψ(1)⟩ + 22n−1 ⟨Ψ(2)| W −,(2) |Ψ(2)⟩ . (35) The first term is estimated using a Hadamard test with unitary UW +,(1) acting...

work page

[13] [13]

SOS vs. HTAAC-QSOS To test the performance of HTAAC-QSOS against SOS, we generate several Max-3SAT instances by draw- ing variables from a uniform distribution and removing clauses with repeating variables. The SOS techniques

work page

[14] [14]

We choose problems with 20 variables each because they may be approximated by SOS within reasonable time

are used to obtain classical solutions. We choose problems with 20 variables each because they may be approximated by SOS within reasonable time. We remark that SOS often yields very tight upper bounds, frequently finding the optimal solution [9, 38]. However, since these upper bounds do not necessarily correspond to feasible solutions, we use a rounding ...

work page

[15] [15]

HTAAC-QSOS To gauge the performance of HTAAC-QSOS for larger problems, we draw instances with 70 to 110 variables from the 2016 MaxSAT evaluation [26]

Classical Heuristic vs. HTAAC-QSOS To gauge the performance of HTAAC-QSOS for larger problems, we draw instances with 70 to 110 variables from the 2016 MaxSAT evaluation [26]. Since classical SOS is intractable for larger problems, the best known so- lutions are given by the winning heuristic solutions from the MaxSAT evaluation. These solvers primarily l...

work page 2016

[16] [16]

multiple register

Evaluating the Objective Max-kSAT can be expressed as a degree-2 D polyno- mial optimization problem, where 2 D = 2 ceil( k/2) is the maximum degree of the polynomial objective 6. The 6 We remind the reader that Max- kSAT can also be expressed as a degree- k polynomial optimization problem, but we introduce 11 Max-3SAT Instance HTAAC-QSOS (SEE) HTAAC-QSOS...

work page

[17] [17]

Thus, the number of mea- surements required to approximately enforce constraints is independent of k

Approximate Amplitude Constraints The Pauli strings and the population-balancing uni- tary are formulated identically to those in Max-3SAT (see Section III A 2), since the equality constraint in the opti- mization problem is the same. Thus, the number of mea- surements required to approximately enforce constraints is independent of k

work page

[18] [18]

(36) can be generalized to DX d=1 2nd−1 α ⟨σz anc.⟩⊗H W +,(d) − ⟨σz anc.⟩W −,(d) , (40) where we recall D = ceil( k/2) and each term may be evaluated with a Hadamard test

Retrieving Solutions The un-rounded SEE solution for Max-3SAT in Eq. (36) can be generalized to DX d=1 2nd−1 α ⟨σz anc.⟩⊗H W +,(d) − ⟨σz anc.⟩W −,(d) , (40) where we recall D = ceil( k/2) and each term may be evaluated with a Hadamard test. We therefore require O(k) = O(D) Hadamard tests to determine this un- rounded solution. The second rounding method f...

work page

[19] [19]

T. L. Patti, J. Kossaifi, A. Anandkumar, and S. F. Yelin, Quantum goemans-williamson algorithm with the hadamard test and approximate amplitude constraints, Quantum 7, 1057 (2023)

work page 2023

[20] [20]

Biamonte, P

J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum machine learning, Na- ture 549, 195–202 (2017)

work page 2017

[21] [21]

Y. Cao, J. Romero, J. P. Olson, M. Degroote, P. D. John- son, M. Kieferov´ a, I. D. Kivlichan, T. Menke, B. Per- opadre, N. P. D. Sawaya, S. Sim, L. Veis, and A. Aspuru- Guzik, Quantum chemistry in the age of quantum com- puting, Chemical Reviews 119, 10856–10915 (2019)

work page 2019

[22] [22]

Montanaro, Quantum algorithms: an overview, npj Quantum Information 2, 1–8 (2016)

A. Montanaro, Quantum algorithms: an overview, npj Quantum Information 2, 1–8 (2016)

work page 2016

[23] [23]

Preskill, Quantum computing in the nisq era and be- yond, Quantum 2, 79 (2018)

J. Preskill, Quantum computing in the nisq era and be- yond, Quantum 2, 79 (2018)

work page 2018

[24] [24]

Korte and J

B. Korte and J. Vygen, Introduction, in Combinatorial Optimization: Theory and Algorithms (Springer, Berlin, Heidelberg, 2018) p. 1–13

work page 2018

[25] [25]

J. Berg, A. Hyttinen, and M. J¨ arvisalo, Applications of maxsat in data analysis, in EPiC Series in Computing , Vol. 59 (EasyChair, 2019) p. 50–64

work page 2019

[26] [26]

Vandenberghe and S

L. Vandenberghe and S. Boyd, Semidefinite program- ming, SIAM Review 38, 49–95 (1996). 13

work page 1996

[27] [27]

V. V. Vazirani, Approximation Algorithms (Springer Link, 2001)

work page 2001

[28] [28]

F. G. S. L. Brand˜ ao, R. Kueng, and D. S. Fran¸ ca, Faster quantum and classical sdp approximations for quadratic binary optimization, Quantum 6, 625 (2022)

work page 2022

[29] [29]

F. G. Brandao and K. M. Svore, Quantum speed-ups for solving semidefinite programs, in 2017 IEEE 58th An- nual Symposium on Foundations of Computer Science (FOCS) (2017) p. 415–426

work page 2017

[30] [30]

J. v. Apeldoorn, A. Gily´ en, S. Gribling, and R. d. Wolf, Quantum sdp-solvers: Better upper and lower bounds, Quantum 4, 230 (2020)

work page 2020

[31] [31]

van Apeldoorn and A

J. van Apeldoorn and A. Gily´ en, Improvements in quantum sdp-solving with applications, in DROPS- IDN/v2/document/10.4230/LIPIcs.ICALP.2019.99 (Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2019)

work page doi:10.4230/lipics.icalp.2019.99 2019

[32] [32]

Ebadi, A

S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuleti´ c, and M. D. Lukin, Quantum optimization of maximum independent set using rydberg atom arrays, Science ...

work page 2022

[33] [33]

F. G. S. L. Brand˜ ao, A. Kalev, T. Li, C. Y.- Y. Lin, K. M. Svore, and X. Wu, Quantum sdp solvers: Large speed-ups, optimality, and applications to quantum learning, in DROPS- IDN/v2/document/10.4230/LIPIcs.ICALP.2019.27 (Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2019)

work page doi:10.4230/lipics.icalp.2019.27 2019

[34] [34]

Patel, P

D. Patel, P. J. Coles, and M. M. Wilde, Vari- ational quantum algorithms for semidefinite pro- gramming, arXiv 10.48550/arXiv.2112.08859 (2021), arXiv:2112.08859 [quant-ph]

work page doi:10.48550/arxiv.2112.08859 2021

[35] [35]

Albash and D

T. Albash and D. A. Lidar, Adiabatic quantum compu- tation, Reviews of Modern Physics 90, 015002 (2018)

work page 2018

[36] [36]

A Quantum Approximate Optimization Algorithm

E. Farhi, J. Goldstone, and S. Gutmann, A quan- tum approximate optimization algorithm, arXiv 10.48550/arXiv.1411.4028 (2014)

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1411.4028 2014

[37] [37]

Quantum Computation by Adiabatic Evolution

E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution, arXiv 10.48550/arXiv.quant-ph/0001106 (2000)

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.quant-ph/0001106 2000

[38] [38]

Gibney, D-wave upgrade: How scientists are using the world’s most controversial quantum computer, Na- ture 541, 447–448 (2017)

E. Gibney, D-wave upgrade: How scientists are using the world’s most controversial quantum computer, Na- ture 541, 447–448 (2017)

work page 2017

[39] [39]

Kadowaki and H

T. Kadowaki and H. Nishimori, Quantum annealing in the transverse ising model, Physical Review E 58, 5355–5363 (1998)

work page 1998

[40] [40]

J. M. Arrazola, V. Bergholm, K. Br´ adler, T. R. Brom- ley, M. J. Collins, I. Dhand, A. Fumagalli, T. Gerrits, A. Goussev, L. G. Helt, J. Hundal, T. Isacsson, R. B. Israel, J. Izaac, S. Jahangiri, R. Janik, N. Killoran, S. P. Kumar, J. Lavoie, A. E. Lita, D. H. Mahler, M. Menotti, B. Morrison, S. W. Nam, L. Neuhaus, H. Y. Qi, N. Que- sada, A. Repingon, K....

work page 2021

[41] [41]

Cerezo, A

M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Variational quantum algo- rithms, Nature Reviews Physics 3, 625–644 (2021)

work page 2021

[42] [42]

Bittel and M

L. Bittel and M. Kliesch, Training variational quan- tum algorithms is np-hard, Physical Review Letters 127, 120502 (2021)

work page 2021

[43] [43]

Cai and X

S. Cai and X. Zhang, Pure maxsat and its applications to combinatorial optimization via linear local search, in Principles and Practice of Constraint Programming , edited by H. Simonis (Springer International Publishing, Cham, 2020) p. 90–106

work page 2020

[44] [44]

of the 19th International Conference on Theory and A

O. of the 19th International Conference on Theory and A. of Satisfiability Testing, The homepage of eighth max-sat evaluation, http://maxsat.ia.udl.cat/ introduction/ (2016)

work page 2016

[45] [45]

P. A. Parrilo, Semidefinite programming relaxations for semialgebraic problems, Mathematical Programming 96, 293–320 (2003)

work page 2003

[46] [46]

M. X. Goemans and D. P. Williamson, Improved approx- imation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM 42, 1115–1145 (1995)

work page 1995

[47] [47]

Hickey and F

R. Hickey and F. Bacchus, Large neighbourhood search for anytime maxsat solving, in Proceedings of the Thirty- First International Joint Conference on Artificial Intel- ligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022 , edited by L. D. Raedt (ijcai.org, 2022) pp. 1818–1824

work page 2022

[48] [48]

A. A. Ahmadi, Sum of squares (sos) techniques: An in- troduction

work page

[49] [49]

Prajna, A

S. Prajna, A. Papachristodoulou, and P. Parrilo, Intro- ducing sostools: a general purpose sum of squares pro- gramming solver, in Proceedings of the 41st IEEE Con- ference on Decision and Control, 2002. , Vol. 1 (2002) p. 741–746 vol.1

work page 2002

[50] [50]

Harrach, Solving an inverse elliptic coefficient prob- lem by convex non-linear semidefinite programming, Op- timization Letters 16, 1599–1609 (2022)

B. Harrach, Solving an inverse elliptic coefficient prob- lem by convex non-linear semidefinite programming, Op- timization Letters 16, 1599–1609 (2022)

work page 2022

[51] [51]

A. Gepp, G. Harris, and B. Vanstone, Financial applica- tions of semidefinite programming: a review and call for interdisciplinary research, Accounting and Finance 60, 3527–3555 (2020)

work page 2020

[52] [52]

S. A. Cook, The complexity of theorem-proving proce- dures, in Proceedings of the third annual ACM sympo- sium on Theory of computing , STOC ’71 (Association for Computing Machinery, New York, NY, USA, 1971) p. 151–158

work page 1971

[53] [53]

Howson, Logic with Trees: An Introduction to Sym- bolic Logic (Routledge, New York, 1997)

C. Howson, Logic with Trees: An Introduction to Sym- bolic Logic (Routledge, New York, 1997)

work page 1997

[54] [54]

Lemon, A

A. Lemon, A. M.-C. So, and Y. Ye, Low-rank semidef- inite programming: Theory and applications, Founda- tions and Trends in Optimization 2, 1–156 (2016)

work page 2016

[55] [55]

Hakemi, M

S. Hakemi, M. Houshmand, E. KheirKhah, and S. A. Hosseini, A review of recent advances in quantum- inspired metaheuristics, Evolutionary Intelligence 17, 627–642 (2024)

work page 2024

[56] [56]

van Maaren, L

H. van Maaren, L. van Norden, and M. J. H. Heule, Sums of squares based approximation algorithms for max-sat, Discrete Applied Mathematics 156, 1754–1779 (2008)

work page 2008

[57] [57]

M. B. Hastings, Perturbation theory and the sum of squares, arXiv (2024), arXiv:2205.12325 [cond-mat, physics:hep-th, physics:quant-ph]

work page arXiv 2024

[58] [58]

A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri, Com- plete family of separability criteria, Physical Review A 69, 022308 (2004). 14 Appendix A: Sum-of-Squares (SOS) and Rounding Procedures In this section of the appendix, we provide more de- tails on the sum-of-squares (SOS) method as well as its rounding procedures

work page 2004

[59] [59]

Let F (y) be a multivariate polynomial, where y de- notes the N variables {yi}i∈{0,1,...,N −1}

SOS Hierarchy While there exist several relaxation algorithms and rounding procedures used to approximate solutions to Max-kSAT and similar problems, we choose SOS as the most standard and systematic method as a classical benchmark for our algorithm. Let F (y) be a multivariate polynomial, where y de- notes the N variables {yi}i∈{0,1,...,N −1}. The goal o...

work page

[60] [60]

In this way, the problem becomes the SDP maximize Q ∈ S+ ⟨W, Q⟩ subject to bbT , Q = F (y) (A9) where W is defined such that ⟨W, Q⟩ ∝ γ

Specifically, we define b ≡ 1 y0 y1 y2 y3 y0y1 y2y3 T (A8) and determine Q as a function of γ and the coefficients of ti(y) such that F (y) is SOS, that is, F (y) = bT Qb = bbT , QT . In this way, the problem becomes the SDP maximize Q ∈ S+ ⟨W, Q⟩ subject to bbT , Q = F (y) (A9) where W is defined such that ⟨W, Q⟩ ∝ γ. Solving the SDP, we obtain an upper ...

work page

[61] [61]

[38], and the steps are as follows

Rounding Procedures The rounding procedure used in our SOS solution is equivalent one of the rounding procedures described by van Maaren et al. [38], and the steps are as follows. It can be shown that the optimal solution Q of the SOS method described in the previous section has an eigen- value zero. We determine the orthogonal basis of eigen- vectors v1,...

work page