Light Cone Cancellation for Variational Quantum Eigensolver in Solving Noisy Max-Cut

Xinwei Lee, Xinjian Yan, Ningyi Xie, Yoshiyuki Saito, Leo Kurosawa, Nobuyoshi Asai, Ran Dong, Hoong Chuin LauResearch Square 2025 · DOI

TL;DR

Researchers have successfully applied Light Cone Cancellation (LCC) to the Variational Quantum Eigensolver (VQE) to solve the Max-Cut problem on up to 100 nodes using only 5-qubit subcircuits. By mathematically pruning redundant quantum gates, this approach significantly mitigates hardware noise and allows large-scale optimization problems to be tackled on today’s limited, noisy quantum devices.

What Problem Does This Paper Address?

The Max-Cut problem—finding a way to partition a graph's nodes into two sets such that the number of edges between them is maximized—is a classic NP-hard challenge with applications ranging from network design to VLSI layout. While Variational Quantum Algorithms (VQAs) like VQE are promising candidates for solving such problems on Noisy Intermediate-Scale Quantum (NISQ) hardware, they face a massive hurdle: noise.

As the size of the problem (the number of nodes) grows, the required number of qubits and quantum gates increases. In the NISQ era, more gates mean more decoherence and gate errors, which quickly wash out any potential quantum advantage. The authors sought a way to solve large-scale Max-Cut problems without needing a massive, perfectly coherent quantum computer.

Methods

The core innovation is the integration of Light Cone Cancellation (LCC) into the VQE framework.

  1. LCC Logic: When calculating the "expectation value" (the average outcome) of a local interaction between two qubits, many gates in the overall circuit have no physical impact on that specific result. LCC identifies and "cancels" these redundant gates.
  2. Circuit Decomposition: By applying LCC, a massive quantum circuit can be broken down into several much smaller subcircuits. For a standard "two-local" ansatz (a specific circuit structure), the authors proved that any Max-Cut problem, regardless of size, can be decomposed into subcircuits requiring at most 5 qubits.
  3. Hybrid Optimization: The algorithm remains hybrid. Small quantum subcircuits calculate local energy contributions, and a classical optimizer (COBYLA) updates the parameters to find the global minimum.
  4. Ansatz Choice: The study focused on a single-layer "two-local" ansatz with circular entanglement, which provides a balance between expressibility and simplicity.

Datasets

The authors evaluated their method using two types of unweighted, undirected graphs:

  • Regular Graphs: Graphs where every node has the same number of neighbors (degree d).
  • Erdős-Rényi Graphs ($G(n, p)$): Random graphs where edges exist with a probability p.
  • Hardware Simulators: To test noise mitigation, they used Qiskit’s "fake" backends—FakeCasablanca (7 qubits) and FakeParis (27 qubits)—which mimic the noise profiles of real IBM Quantum processors.

Key Insights and Ideas

  • The "5-Qubit Magic": Perhaps the most striking insight is that for a single-layer circular ansatz, you don't need a 100-qubit machine to solve a 100-node problem. You only need to simulate 5-qubit subcircuits. This shifts the complexity from exponential qubit scaling to polynomial classical scaling.
  • Noise Mitigation through Reduction: LCC isn't just a trick for smaller simulators; it’s a physical noise mitigation strategy. By removing redundant gates, you remove sources of error. The results showed that LCC-VQE consistently achieved higher approximation ratios than standard VQE on noisy backends.
  • The "Less is More" Ansatz: The researchers found that adding more layers to the VQE ansatz actually decreased the quality of the solution. This is likely due to "overparameterization," where the classical optimizer gets stuck in local minima because the landscape becomes too complex. A single-layer ansatz was sufficient and more robust.

Key Results

  • Superiority over Standard VQE: In noisy simulations (10 to 15 nodes), LCC-VQE maintained a much higher approximation ratio (AR) than standard VQE. Standard VQE's performance decayed rapidly as the circuit grew, while LCC-VQE remained stable.
  • Scaling to 100 Qubits: The authors successfully demonstrated LCC-VQE on 100-node graphs, a feat that would be impossible for standard VQE on current NISQ simulators without LCC.
  • Beating Classical Benchmarks: When compared to the famous classical Goemans-Williamson (GW) algorithm in noiseless conditions, LCC-VQE performed better on denser graphs (those with higher degrees or higher edge probabilities). While GW is excellent for sparse graphs, VQE showed a "steadily increasing trend" in accuracy as graph density increased.

Limitations and Future Work

  • Entanglement Constraints: LCC is highly dependent on the circuit architecture. It works beautifully for linear or circular entanglement but is "not feasible under full entanglement" (where every qubit connects to every other qubit), as the "light cone" would eventually encompass the entire circuit.
  • Classical Optimization Bottleneck: While the quantum side is simplified, the classical optimizer still faces a non-convex landscape. Finding the absolute global minimum remains a challenge as the number of parameters grows.
  • Future Directions: The authors suggest exploring LCC with other VQAs and testing the method on different combinatorial optimization problems beyond Max-Cut to see if the "constant qubit" advantage holds.

Summary updated

Abstract

<title>Abstract</title> Variational Quantum Eigensolver (VQE) is a quantum-classical hybrid algorithm used to estimate the ground energy of a given Hamiltonian. It consists of a parameterized quantum circuit, which the parameters are optimized using a classical optimizer. With the increasing need in solving large-scale problems in real-world applications, solving those large problems with fewer qubits and fewer gates becomes essential, so that we reduce the simulation difficulty and mitigate the effect of noise in real quantum hardware. In this study, we applied the Light Cone Cancellation (LCC) method to reduce the number of qubits and gates required in a two-local ansatz. LCC removes redundant gates that are not required in the calculation of the expectation value for a local observable. This leads to two consequences: 1) the quantum circuit used to create the trial wavefunction of VQE can be broken down into multiple quantum subcircuits with fewer qubits, enabling large-scale problems to be solved without actually simulating the entire circuit; and 2) reduced number of quantum gates in the circuit leads to the noise mitigation in quantum hardware. The main purpose of this work is to demonstrate the effectiveness of this method (called the LCC-VQE) in mitigating the device noise when solving the Max-Cut problem up to 100 qubits, using simulations on small (7-qubit and 27-qubit) fake noisy backends. Employing a single-layer two-local ansatz circuit architecture, the reuslts show that LCC-VQE yields higher approximation ratios than those cases without LCC, implying that the effect of noise is mitigated when LCC is applied. An analysis of more than one layer of two-local ansatz is also performed, but empirical results show that the single-layer ansatz still performs the best among them. We also compare LCC-VQE under noiseless conditions with the Goemans-Williamson algorithm.
BibTeX
@inproceedings{lee2025light,
  author = {Xinwei Lee and Xinjian Yan and Ningyi Xie and Yoshiyuki Saito and Leo Kurosawa and Nobuyoshi Asai and Ran Dong and Hoong Chuin Lau},
  title = {{Light Cone Cancellation for Variational Quantum Eigensolver in Solving Noisy Max-Cut}},
  booktitle = {Research Square},
  year = {2025},
  doi = {10.21203/rs.3.rs-7693543/v1},
}
Figure