2025/10/01 by Kyriienko, Oleksandr, Umeano, Chukwudubem, Holmes, Zoë
#FOS: Computer and information sciences #FOS: Physical sciences #Neural and Evolutionary Computing (cs.NE) #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2510.01154
The relative power of quantum algorithms, using an adaptive access to quantum devices, versus classical post-processing methods that rely only on an initial quantum data set, remains the subject of active debate. Here, we present evidence for an exponential separation between adaptive and non-adaptive strategies in a quantum circuit recompilation task. Our construction features compilation problems with loss landscapes for discrete optimization that are unimodal yet non-separable, a structure known in classical optimization to confer exponential advantages to adaptive search. Numerical experiments show that optimization can efficiently uncover hidden circuit structure operating in the regime of volume-law entanglement and high-magic, while non-adaptive approaches are seemingly limited to exhaustive search requiring exponential resources. These results indicate that adaptive access to quantum hardware provides a fundamental advantage.