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.
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.
We evaluated three variants of PAOA:
- Full PAOA: Utilizes 4 parameters per graph edge.
- Reduced PAOA: Utilizes 1 parameter per edge.
- 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