Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives

This paper introduces Product-State Lifting (PSL), a resource-efficient encoding method that upgrades variational quantum semidefinite programs to solve general $k$-degree polynomial optimization problems with only a linear increase in resources, thereby overcoming the scalability limitations of classical relaxations.

The Gist

The Big Picture: Solving Hard Puzzles with Quantum Help

Imagine you are trying to solve a massive, incredibly difficult puzzle (like finding the best way to schedule every flight in the world or cracking a complex code). In the world of math, these are called NP-hard problems. They are so hard that even the fastest supercomputers take forever to solve them perfectly.

To get around this, scientists use "shortcuts" called approximation algorithms. They don't look for the perfect answer; they look for a very good answer that can be found quickly.

For decades, the best shortcut for these puzzles has been a method called Semidefinite Programming (SDP). Think of SDP as a master key that works great for puzzles made of quadratic pieces (pieces that interact in pairs, like two people shaking hands).

The Problem:
Many real-world puzzles aren't just about pairs. They involve groups of three, four, or even more things interacting at once (like a group chat where everyone influences everyone else). In math terms, these are higher-order polynomial problems.

• The Old Way: To use the master key (SDP) on these complex puzzles, classical computers have to break the big group interactions down into tiny pairs. This is like trying to describe a complex dance by only describing who is holding hands with whom. It forces the computer to create a massive, bloated list of rules, making the puzzle huge, slow, and messy.

The Quantum Solution:
This paper introduces a new trick called Product-State Lifting (PSL). It allows quantum computers to handle these complex, multi-person interactions directly, without breaking them down into messy pairs.

---

The Core Idea: The "Copy-Paste" Trick

The authors propose a clever way to upgrade quantum computers so they can solve these "group" puzzles efficiently. Here is how it works, using an analogy:

1. The Old Quantum Method (The Single Actor)

Imagine a quantum computer is a stage with a single actor (a qubit register). This actor can play many different roles (representing different variables in your puzzle).

• The Limitation: If the puzzle requires the actor to interact with themselves in a complex way (like a group of 3 people), the single actor has to pretend to be all three people at once. It gets confusing, and the math gets messy.

2. The New Method: Product-State Lifting (The Mirror Room)

The authors say: "Why make the actor pretend? Let's just bring in more actors!"

• The Trick: If your puzzle involves a group of 3 interacting variables, the quantum computer prepares 3 identical copies of the actor on stage.
• The Magic: Because these copies are identical, they naturally "know" how to interact with each other. If Actor A touches Actor B, and Actor B touches Actor C, the math works out perfectly because they are all the same person.
• The Result: You don't need to write down thousands of extra rules to force them to behave. The "group" behavior happens naturally because you simply duplicated the setup.

The "Lifting" Part:
The word "Lifting" here means taking a simple, flat puzzle (quadratic) and "lifting" it up to a more complex, 3D shape (polynomial) without making the puzzle bigger.

• Classical Approach: To solve a 3-way puzzle, you might need a library the size of a city.
• PSL Approach: You just add two more identical rooms to your house. The size of the house grows linearly (1 room $\to$ 3 rooms), not exponentially.

---

Why This Matters: The "Max-kSAT" Test

To prove their idea works, the authors tested it on a classic puzzle called Max-kSAT.

• The Puzzle: You have a list of logical rules (clauses) involving "True" or "False" switches. Your goal is to flip the switches to satisfy as many rules as possible.
• The Challenge: In "Max-3SAT," rules involve 3 switches at once. In "Max-kSAT," they involve $k$ switches.

What they found:

1. Better than Classical Shortcuts: For small puzzles, their quantum method (simulated on a classical computer) found better solutions than the best classical "shortcuts" (called Sum-of-Squares).
2. Scalable: Unlike classical methods that get stuck when the puzzle gets too big, this quantum method stays manageable. It scales linearly, meaning if you double the complexity of the group interaction, you only double the resources needed, not square them.
3. Consistency: Because the method uses identical copies, the math stays "honest." In classical methods, when you round off numbers to get a final answer, you often lose the logical consistency (e.g., the math says A and B are friends, but B and C are enemies, which breaks the logic). The quantum "copy" method keeps the logic consistent naturally.

The "Hadamard Test": The Quantum Microscope

How do they actually measure the answer? They use a tool called the Hadamard Test.

• Analogy: Imagine you have a complex machine with many gears. You want to know how fast it's spinning, but you can't touch the gears.
• The Tool: You attach a tiny, sensitive sensor (an "ancilla" qubit) to the machine. You give the machine a little nudge and watch how the sensor vibrates.
• The Result: By measuring that tiny vibration, you can calculate the speed of the whole machine without having to look at every single gear. This allows the quantum computer to evaluate the complex "group" interactions efficiently.

The Bottom Line

This paper presents a "plug-and-play" upgrade for quantum computers.

• Before: Quantum computers could only easily solve puzzles where things interacted in pairs.
• Now: With Product-State Lifting (PSL), we can upgrade any existing quantum solver to handle puzzles where things interact in groups of 3, 4, or more, with very little extra cost.

It's like upgrading a bicycle to carry a passenger. You don't need to build a whole new vehicle; you just add a sidecar (the extra copies), and suddenly, you can carry more weight without the engine straining. This opens the door for quantum computers to solve much more complex real-world problems in logistics, drug discovery, and artificial intelligence.

Technical Summary

1. Problem Statement

Many practically important NP-hard optimization problems (e.g., Max-kSAT, polynomial knapsack, k-local Ising models) are inherently higher-order polynomial optimizations (degree $k > 2$).

• Classical Limitations: Standard classical approaches, such as Sum-of-Squares (SOS) hierarchies, handle these by relaxing the problem into a quadratic form. However, this "lifting" to a quadratic proxy significantly inflates the problem size (the number of variables and constraints grows exponentially or unfavorably with the polynomial degree), degrading approximation behavior and making large-scale problems intractable.
• Quantum Limitations: While Variational Quantum Semidefinite Programs (vQSDPs) have been proposed to solve quadratic objectives on near-term quantum devices, they are currently limited to degree-2 (quadratic) problems. Existing quantum SDP solvers (QSDPs) require deep circuits and are unsuitable for noisy intermediate-scale quantum (NISQ) hardware.

The Core Challenge: How to extend vQSDPs to handle $k$-degree polynomial objectives natively without the exponential resource explosion typical of classical relaxations.

2. Methodology: Product-State Lifting (PSL)

The authors introduce Product-State Lifting (PSL), a novel encoding scheme that upgrades any basis-state vQSDP to solve $k$-degree polynomial optimization problems.

Key Technical Components:

• Even-Degree Transformation: Any polynomial objective can be converted to an even-degree polynomial (degree $2D$) by introducing a dummy variable (analogous to $y_0$ in Max-kSAT formulations). This allows the method to focus on even-degree monomials.
• Tensor-Product Encoding: Instead of expanding the basis or adding new constraints, PSL represents a degree-$2d$ term by preparing $d$ identical copies of the same $n$-qubit quantum state $\rho = |\psi\rangle\langle\psi|$.
  • Mathematically, a degree-$2d$ term is encoded in the tensor product state $\rho^{\otimes d}$.
  • For example, a degree-4 term ($y_i y_j y_q y_l$) is represented by the expectation value over $\rho \otimes \rho$.
• Algebraic Consistency: Unlike classical SOS, which requires additional constraints to enforce moment consistency (e.g., ensuring $E[y_i y_j] = E[y_i]E[y_j]$ where appropriate), PSL inherently enforces algebraic consistency. Since every register is an identical copy of the base state $\rho$, the product structure is guaranteed by construction.
• Resource Scaling:
  • Qubits: Requires $O(nk)$ qubits (linear increase with degree $k$).
  • Constraints: The number of constraints remains constant regardless of the polynomial degree. The constraint machinery (Pauli strings and population-balancing unitaries) used for the quadratic case applies directly to the lifted case without modification.
  • Measurements: Requires $O(k)$ Hadamard tests to evaluate the objective function.

Algorithmic Workflow:

1. Encoding: The problem is mapped to a degree-$2D$ polynomial.
2. State Preparation: A variational circuit $U_V$ prepares an $n$-qubit state $|\psi\rangle$.
3. Objective Evaluation:
   • For degree-$2d$ terms, $d$ copies of $|\psi\rangle$ are prepared.
   • A Hadamard test is performed on the combined system ($nd$ qubits) using a unitary $U_W = e^{i\alpha W}$ to estimate the expectation value $\text{Im}(\langle \psi|^{\otimes d} U_W |\psi\rangle^{\otimes d})$.
4. Optimization: The loss function (objective + penalty terms for constraints) is minimized variationally.
5. Solution Extraction:
   • Sample-Efficient (SE): Directly estimates the unrounded solution from expectation values.
   • State Tomography (ST): Reconstructs the density matrix $\rho$ to extract a feasible, rounded solution (e.g., $y_i = \text{sign}(\psi_i)$).

3. Key Contributions

1. PSL Framework: A general, device-friendly method to elevate vQSDPs from quadratic to arbitrary polynomial degrees with only linear resource growth in $k$.
2. Native Polynomial Handling: Eliminates the need for classical "quadratic proxies" that inflate problem size, preserving the native structure of polynomial objectives.
3. Constraint Efficiency: Demonstrates that algebraic consistency is maintained by the tensor-product structure, removing the need for the complex constraint hierarchies required by SOS.
4. Application to Max-kSAT: Successfully applied the framework to Max-3SAT (and generalized to Max-kSAT), a standard benchmark for higher-order optimization.

4. Results

The authors performed classical simulations of the variational loop for Max-3SAT instances (up to 110 variables and 1500 clauses).

• Comparison with Classical SOS (Small Problems):
  • For problems with 20 variables, the PSL-based approach consistently achieved rounded solutions equal to or better than classical SOS solutions.
  • Crucially, PSL did not suffer from the "rounding degradation" often seen in SOS, where the relaxation gap widens significantly after rounding.
• Comparison with Classical Heuristics (Large Problems):
  • For larger instances (70–110 variables), where SOS is intractable, the PSL approach was compared against state-of-the-art MaxSAT heuristic solvers.
  • The PSL approach achieved solutions within ~98-99% of the best known heuristic results.
  • While slightly behind specialized heuristics in raw score, the PSL method offers a theoretical guarantee and a generalizable framework, whereas heuristics are often problem-specific.
• Scalability: The simulations confirmed that the approach is tractable for problem sizes where classical SOS fails, and the unrounded solutions showed strong correlation with the loss function.

5. Significance and Future Directions

• Bridging the Gap: PSL provides a general path from quadratic to polynomial optimization on near-term quantum devices without the constraint explosion typical of classical relaxations.
• Quantum-Inspired Algorithms: The authors suggest that the PSL framework, even when simulated classically, acts as a powerful "quantum-inspired" algorithm. It offers a new template for classical optimization that avoids the rank-deficiency issues of standard SDP relaxations (since the solution is always a pure state, i.e., rank-1).
• Generality: The method is not limited to Max-kSAT; it can be applied to any polynomial optimization problem, including those over continuous variables (e.g., in quantum chemistry or reduced density matrix methods).
• Future Work: The authors propose formalizing convergence guarantees for the lifted observables, testing on harder benchmark suites, and developing quantum-inspired variants that bypass the need for quantum hardware while retaining the PSL structural advantages.

In summary, this work presents a scalable, resource-efficient method to tackle high-degree polynomial optimization on quantum hardware, overcoming a major bottleneck in applying variational algorithms to complex combinatorial problems.