Quantum optimization of maximum independent set using Rydberg atom arrays

Area of Science:

• Quantum information science
• Quantum computing
• Computational complexity

Background:

• Solving computationally hard problems is a key challenge.
• Quantum algorithms offer potential for speedups.
• Rydberg atom arrays are a promising platform for quantum computation.

Purpose of the Study:

• To experimentally investigate quantum algorithms for the maximum independent set problem.
• To explore the performance of these algorithms on programmable graphs using Rydberg atom arrays.
• To benchmark quantum performance against classical methods.

Main Methods:

• Utilized Rydberg atom arrays with up to 289 qubits.
• Employed a hardware-efficient encoding leveraging Rydberg blockade.
• Implemented closed-loop optimization for variational quantum algorithms.
• Tested algorithms on graphs with programmable connectivity.
• Benchmarked against classical simulated annealing.

Main Results:

• Identified solution degeneracy and local minima as key factors in problem hardness.
• Observed a superlinear quantum speedup in finding exact solutions for the hardest graphs.
• Analyzed the origins of the observed quantum speedup in the deep circuit regime.

Conclusions:

• Rydberg atom arrays can experimentally realize quantum algorithms for hard computational problems.
• Quantum algorithms show potential for significant speedup over classical methods for specific problem instances.
• The study provides insights into the performance and scalability of quantum approaches for combinatorial optimization.