Adaptive quantum computers Decoding and state preparation

Since the first concepts of computers emerged in the late 19th century, significant advances have been made. Lately, interest in so-called quantum computers is rising, due to their potential in solving specific problems significantly faster than current methods can. Future quantum computers will have to interact with a standard computer to operate effectively. Even though current quantum computers are still under development and have limited capabilities, the interaction with a standard computer can already enhance their functionality, particularly by offloading certain computations to the standard computer. Quantum computers that interact with standard computers to perform computations are called adaptive quantum computers.
This work shows that adaptive quantum computers are more powerful than standard computers by showing that the former is better at retrieving information from corrupted digital data provided only a fixed number of computation steps is allowed. The proof uses a structure-versus-randomness approach from additive combinatorics that splits the problem in a structured and a random-like component and gives an explicit adaptive quantum circuit that retrieves the information. Additionally, this work shows that adaptive quantum computers are more efficient than non-adaptive quantum computers with respect to preparing specific quantum states. Specifically, this work gives explicit adaptive constructions for the uniform superposition state, the GHZ state, the W-state and the Dicke state. These states are often used in other quantum algorithms, so having efficient routines for preparing them also enhance the efficiency of other algorithms. This work concludes by comparing these adaptive quantum computations with non-adaptive ones, analyzing their performance both theoretically and through quantum hardware implementations.