Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints

I. Wang, Robin Brown, Taylor L. Patti, Anima Anandkumar, Marco Pavone, Susanne F. YelinarXiv 2024 · DOI · arXiv

Abstract

Quantum computation shows promise for addressing numerous classically intractable problems, such as optimization tasks. Many optimization problems are NP-hard, meaning that they scale exponentially with problem size and thus cannot be addressed at scale by traditional computing paradigms. The recently proposed quantum algorithm arXiv:2206.14999 addresses this challenge for some NP-hard problems, and is based on classical semidefinite programming (SDP). In this manuscript, we generalize the SDP-inspired quantum algorithm to sum-of-squares programming, which targets a broader problem set. Our proposed algorithm addresses degree-$k$ polynomial optimization problems with $N \leq 2^n$ variables (which are representative of many NP-hard problems) using $O(nk)$ qubits, $O(k)$ quantum measurements, and $O(\textrm{poly}(n))$ classical calculations. We apply the proposed algorithm to the prototypical Max-$k$SAT problem and compare its performance against classical sum-of-squares, state-of-the-art heuristic solvers, and random guessing. Simulations show that the performance of our algorithm surpasses that of classical sum-of-squares after rounding. Our results further demonstrate that our algorithm is suitable for large problems and approximates the best known classical heuristics, while also providing a more generalizable approach compared to problem-specific heuristics.

Introduction: The Challenge of High-Degree Optimization

Many real-world challenges—from logistics to drug discovery—boil down to NP-hard combinatorial optimization problems. While classical computers can approximate quadratic problems (like Max-2SAT) using Semidefinite Programming (SDP), higher-degree problems (like Max-kSAT where $k > 2$) require a more complex tool called Sum-of-Squares (SOS) programming.

Comparison of classical and quantum optimization frameworks.

Classical SOS is computationally "heavy." As the degree of the polynomial increases, the size of the matrices involved grows polynomially, but the exponent is tied to the degree, making it intractable for large-scale industrial problems. Existing quantum approaches often require an exponential number of measurements or qubits, limiting their utility on near-term hardware. This paper introduces HTAAC-QSOS (Hadamard Test and Approximate Amplitude Constraints - Quantum Sum-of-Squares), a quantum algorithm that is more general than SDP-based methods but more efficient than brute-force classical SOS.

The HTAAC-QSOS Framework

HTAAC-QSOS generalizes semidefinite programming to higher-degree polynomial optimization using the SOS framework. The algorithm achieves performance that surpasses classical SOS after rounding and rivals state-of-the-art heuristics, all while maintaining a resource-efficient scaling of $O(nk)$ qubits for a degree-$k$ problem.

Workflow of the HTAAC-QSOS algorithm.

The workflow of HTAAC-QSOS involves several innovative components:

  • Product State Encoding: To represent higher-degree terms (like $y_i y_j y_q y_l$), the algorithm uses a "multiple register" approach. It prepares $d$ identical copies of a quantum state $\rho$. The degree-$2d$ terms are then naturally represented by the product state $\rho^{\otimes d}$. This allows for the evaluation of degree-$k$ terms using $k/2$ subsystems.
  • The Hadamard Test: Instead of full state tomography to find every element of a density matrix, the algorithm uses the Hadamard test to estimate the objective function as a single expectation value on an ancilla qubit. This significantly reduces the measurement overhead.
  • Approximate Amplitude Constraints: To ensure the quantum state actually represents valid bits (enforcing $\rho_{i,i} = 2^{-n}$), the authors use a truncated set of Pauli string constraints and a "population-balancing" unitary. This keeps the number of measurements manageable while maintaining physical validity.
  • Variational Optimization: The parameters of a quantum circuit $U_V$ are iteratively updated to minimize a loss function that combines the objective value and the constraint violations. The total loss is calculated by summing the contributions from the objective evaluation and the approximate amplitude constraints.

Experimental Evaluation

The algorithm was evaluated using two primary datasets to test its scalability and performance:

  1. Randomly generated Max-3SAT instances: Small-scale problems (20 variables) used to compare directly against classical SOS solvers.
  2. 2016 MaxSAT Evaluation Benchmarks: Larger-scale instances (70 to 110 variables, up to 1100 clauses) used to compare against "winning" classical heuristic solvers.

In 20-variable Max-3SAT tests, HTAAC-QSOS consistently outperformed classical SOS after the classical results were rounded to feasible solutions (achieving ~1.04x to 1.08x the objective value). On large-scale problems (110 variables), the algorithm’s rounded solutions were within 3% of the best-known classical heuristic solvers. The researchers also compared two methods for final solution extraction: Full Tomography (FT) for rounded solutions and Sample-Efficient Estimation (SEE) for calculating SAT values, demonstrating flexibility in resource allocation.

Key Insights and Future Outlook

HTAAC-QSOS offers several theoretical and practical advantages over existing methods:

  • Natural Algebraic Consistency: In classical SOS, rounding a solution often breaks "algebraic consistency"—the requirement that the value for $y_i \cdot y_j$ actually equals the product of the rounded values for $y_i$ and $y_j$. Because HTAAC-QSOS uses product states ($\rho \otimes \rho$), this consistency is preserved by construction, leading to superior rounding behavior.
  • Rank-1 Advantage: Classical SDP/SOS relaxations often yield high-rank solutions, which are harder to round accurately. The quantum state in this algorithm is always a pure state (rank-1), which is theoretically the "ideal" form for a relaxed solution.
  • Generalizability: Unlike many classical solvers that are hand-tuned for specific problems like Max-SAT, HTAAC-QSOS is a "metaheuristic"—it can be applied to any polynomial optimization problem without changing the underlying framework.

While promising, future work must address measurement overhead on real NISQ hardware and explore extensions to continuous variable optimization. The results demonstrate that HTAAC-QSOS approximates the best known classical heuristics while providing a more generalizable approach.

Summary updated

Abstract

Quantum computation shows promise for addressing numerous classically intractable problems, such as optimization tasks. Many optimization problems are NP-hard, meaning that they scale exponentially with problem size and thus cannot be addressed at scale by traditional computing paradigms. The recently proposed quantum algorithm arXiv:2206.14999 addresses this challenge for some NP-hard problems, and is based on classical semidefinite programming (SDP). In this manuscript, we generalize the SDP-inspired quantum algorithm to sum-of-squares programming, which targets a broader problem set. Our proposed algorithm addresses degree-$k$ polynomial optimization problems with $N \leq 2^n$ variables (which are representative of many NP-hard problems) using $O(nk)$ qubits, $O(k)$ quantum measurements, and $O(\textrm{poly}(n))$ classical calculations. We apply the proposed algorithm to the prototypical Max-$k$SAT problem and compare its performance against classical sum-of-squares, state-of-the-art heuristic solvers, and random guessing. Simulations show that the performance of our algorithm surpasses that of classical sum-of-squares after rounding. Our results further demonstrate that our algorithm is suitable for large problems and approximates the best known classical heuristics, while also providing a more generalizable approach compared to problem-specific heuristics.
BibTeX
@misc{wang2024sum,
  author = {I. Wang and Robin Brown and Taylor L. Patti and Anima Anandkumar and Marco Pavone and Susanne F. Yelin},
  title = {{Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints}},
  year = {2024},
  eprint = {2408.07774},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2408.07774},
}
Figure