Insights from the Quantum Era - August 2023

Here are some scientific papers that caught our eye this month:

‍

Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization

We begin with a notable study addressed a crucial challenge: the extremely long solving times for specific problem instances using adiabatic algorithms, which are the main contenders for near-term quantum optimization. The study employs ideas from phase transitions and many-body quantum physics to pinpoint problem instances and protocols where the gap to arrive at an MIS close in a superexponential manner. This renders these problems challenging for annealing protocols, both quantum and simulated. Leveraging the concept of many-body quantum scars, initially observed in neutral-atom experiments, the authors incorporate additional Hamiltonian terms and quenches into their protocols. This innovative approach overcomes the complexities of adiabatic state preparation. Overall, this research highlights the ample room for algorithmic exploration within the realm of FPQA (Field Programmable Qubit Array) quantum computers.

Read on ArXiv

‍

Quantum speedup for combinatorial optimization with flat energy landscapes

In this study, a group of authors reexamine the performance of neutral-atom computers in addressing MIS problems. Through meticulous development, these authors present a methodology to assess the effectiveness of adiabatic algorithms alongside a wide range of Monte Carlo-based heuristics. This research represents a significant step forward in identifying problem instances suitable for quantum speed-up, offering a clearer understanding of the spectrum of optimization problems in which neutral-atom quantum hardware can be fundamentally applied.

Read on ArXiv

‍

Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups

a group of researchers located in California and New York also delve into the notion of utilizing neutral atoms to address MIS problems. Notably, these scholars extend the evaluation of quantum annealing algorithms by comparing them with cutting-edge custom and commercial solvers, encompassing both exact and heuristic approaches. While the authors establish that certain problem instances (specifically, those related to the Union-Jack, also known as King’s lattice) are generally manageable through classical means, they also identify criteria and approaches for generating instances that pose challenges orders of magnitude beyond classical solver capabilities, motivating experiments with quantum hardware.

Read on ArXiv