Rigetti Computing Develops Qubit-Efficient Algorithm for Combinatorial Optimization

Key Takeaways

• New algorithm cuts required qubits for optimization tasks.
• Generalizes QAOA ansatz with entangled wave‑function encoding.
• Shows performance guarantees on spin‑glass benchmark.
• Applicable to both NISQ and fault‑tolerant quantum computers.
• DARPA funding validates strategic importance of quantum algorithms.

Summary

Rigetti Computing secured a DARPA contract to advance quantum algorithms for optimization and unveiled a qubit‑efficient method that maps candidate solutions onto entangled wave functions, dramatically reducing the qubit count needed. The technique extends the quantum approximate optimization ansatz and was validated on the notoriously hard Sherrington‑Kirkpatrick spin‑glass problem, delivering provable performance guarantees. Results indicate the approach works on current intermediate‑scale (NISQ) devices and scales to future fault‑tolerant quantum computers. The research, published in Physical Review Applied, signals a practical pathway for near‑term quantum advantage in combinatorial optimization.

Pulse Analysis

Quantum computing’s promise has long been hampered by the scarcity of high‑fidelity qubits, especially for combinatorial optimization tasks that demand large Hilbert spaces. Rigetti Computing’s recent DARPA‑backed project tackles this bottleneck head‑on, introducing a method that encodes candidate bit‑strings directly into entangled wave functions. By compressing the solution space onto fewer qubits, the approach sidesteps the exponential hardware growth that traditionally limits quantum advantage, positioning near‑term devices to address problems once thought exclusive to classical supercomputers.

The technical core of the algorithm builds on the quantum approximate optimization algorithm (QAOA) but generalizes its ansatz to exploit parameter concentration—a phenomenon where optimal circuit parameters converge predictably during training. Tested on the Sherrington‑Kirkpatrick spin‑glass model, a benchmark for NP‑hard optimization, the method demonstrated consistent performance guarantees and reduced circuit depth. This not only improves success probabilities on noisy intermediate‑scale quantum (NISQ) processors but also offers a scalable blueprint for future fault‑tolerant architectures, where qubit efficiency translates directly into lower error correction overhead.

For industry, the implications are immediate. Sectors such as finance, logistics, and materials science, which rely on solving large‑scale combinatorial problems, can now explore quantum‑enhanced solutions without waiting for massive quantum processors. The DARPA endorsement underscores governmental confidence in quantum algorithmic research, likely spurring additional funding and partnerships. As quantum hardware continues to mature, Rigetti’s qubit‑efficient framework could become a foundational tool, accelerating the transition from experimental prototypes to production‑grade quantum optimization services.