Sub-universal variational circuits for combinatorial optimization problems

Gal Weitz, Lirandë Pira, Chris Ferrie, Joshua Combes

Abstract

Quantum variational circuits have gained significant attention due to their applications in the quantum approximate optimization algorithm and quantum machine learning research. This work introduces a novel class of classical probabilistic circuits designed for generating approximate solutions to combinatorial optimization problems constructed using two-bit stochastic matrices. Through a numerical study, we investigate the performance of our proposed variational circuits in solving the Max-Cut problem on various graphs of increasing sizes. Our classical algorithm demonstrates improved performance for several graph types to the quantum approximate optimization algorithm. Our findings suggest that evaluating the performance of quantum variational circuits against variational circuits with sub-universal gate sets is a valuable benchmark for identifying areas where quantum variational circuits can excel.

Introduction

The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate for demonstrating quantum advantage on near-term hardware. It aims to solve combinatorial optimization problems, such as Max-Cut, by leveraging quantum interference and entanglement. However, establishing a clear advantage over classical methods remains challenging. Current benchmarks often compare QAOA against random guessing or highly optimized classical algorithms like Goemans-Williamson, leaving a gap for "fair" comparisons against classical architectures that share a similar variational structure.

The hierarchy of variational circuits, illustrating PAOA as a sub-universal subset within the broader QAOA and PQC frameworks.

Methods

To address this, we propose the Probabilistic Approximate Optimization Algorithm (PAOA). PAOA replaces the qubits and unitary gates of QAOA with classical probabilistic bits (p-bits) and stochastic matrices. While qubits exist in complex superpositions, p-bits represent classical probability distributions. The algorithm utilizes "sub-universal" circuits, which are intentionally limited in computational power, being unable to perform general-purpose quantum or reversible classical computation.

Comparison of the circuit structures for QAOA (Quantum) and PAOA (Classical) applied to the Max-Cut problem.

We evaluated three variants of PAOA:

  1. Full PAOA: Utilizes 4 parameters per graph edge.
  2. Reduced PAOA: Utilizes 1 parameter per edge.
  3. Min PAOA: Utilizes only 2 parameters for the entire circuit, directly mimicking the standard QAOA layer structure.

Results

The performance was tested on various graph topologies, including 2-regular, 3-regular, complete, Barabasi-Albert, and Erdős–Rényi graphs. For small graphs ($n=4$ to $20$), PAOA frequently outperformed QAOA. For instance, on a 20-node 2-regular graph, Reduced PAOA achieved an approximation ratio of 0.93, compared to 0.67 for a single-layer QAOA. On complete graphs, Min PAOA achieved a perfect 1.00 approximation ratio.

Furthermore, PAOA demonstrated excellent scalability. Unlike QAOA simulations, which scale exponentially, PAOA scales linearly with the number of edges. We successfully applied PAOA to graphs with up to 250 nodes on standard classical hardware, maintaining high approximation ratios (~0.85-0.90) and showing lower variance in results compared to QAOA.

Discussion

The superior performance of these sub-universal classical circuits suggests that the "quantumness" of QAOA may not always be the primary driver of its success in standard benchmarks. Instead, the power of the variational framework itself may be sufficient for many problem instances. PAOA provides a robust classical baseline; if a quantum variational algorithm cannot outperform a sub-universal probabilistic circuit, its potential for real-world advantage is questionable. Future work will explore hardware implementations using MRAM-based stochastic devices and identifying specific "hard" graph instances where quantum effects might finally prevail.

Summary updated

Abstract

Quantum variational circuits have gained significant attention due to their applications in the quantum approximate optimization algorithm and quantum machine learning research. This work introduces a novel class of classical probabilistic circuits designed for generating approximate solutions to combinatorial optimization problems constructed using two-bit stochastic matrices. Through a numerical study, we investigate the performance of our proposed variational circuits in solving the Max-Cut problem on various graphs of increasing sizes. Our classical algorithm demonstrates improved performance for several graph types to the quantum approximate optimization algorithm. Our findings suggest that evaluating the performance of quantum variational circuits against variational circuits with sub-universal gate sets is a valuable benchmark for identifying areas where quantum variational circuits can excel.
BibTeX
@misc{weitz2023sub,
  author = {Gal Weitz and Lirandë Pira and Chris Ferrie and Joshua Combes},
  title = {{Sub-universal variational circuits for combinatorial optimization problems}},
  year = {2023},
  eprint = {2308.14981},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2308.14981},
}
Figure