TOWARDS QUANTUM ADVANTAGE AND CERTIFICATION WITH NOISY INTERMEDIATE-SCALE QUANTUM DEVICES

Abstract

The second quantum revolution’s success critically depends on the practical applications of the noisy intermediate-scale quantum devices. Despite the hope rendered by the experimental demonstration of “quantum supremacy”, the essential question regarding how to translate such breakthroughs into quantum advantages for practical use-cases remains unsolved. The search for the “killer app” for the noisy intermediate-scale quantum devices continues, with potential application areas being solid-state physics, quantum chemistry, combinatorial optimization and machine learning. This thesis discusses noisy intermediate-scale quantum algorithms for quantum linear system problem, closed system simulation, and open system simulation. Our algorithms for simulating dynamics do not have a classical-quantum feedback loop and bypass the trainability issues such as the barren plateau problem by construction. Another critical task relevant to the second quantum revolution is evaluating the performance of noisy intermediate-scale quantum devices. This is where device certification and benchmarking come in. Using ideas from quantum foundations, graph theory and optimization theory, we provide a path towards robust device certification schemes based on self-testing. Our certification method is local and can be applied to arbitrary high dimensional quantum systems.