Quantum Supremacy: computational complexity and applications

Jack D. Hidary

Jack D. Hidary

Kamaljit I. Lakhtaria, Vrunda Gadesha

When we aim to demonstrate that a programmable quantum device can solve complex problems which cannot be addressed by classic computers, this fundamental goal is known as quantum supremacy. This concept has changed every fundamental rule of computation. In this chapter, the detailed concept of quantum computing and quantum supremacy is explained along with various open source tools and real-time applications of this technology. The major base concepts, quantum computing, the difference between classical and quantum computer on physical level, programing quantum device, and the experiment-quantum supremacy are explained conceptually. This chapter also includes an introduction of the tools Cirq and OpenFermion plus the applications like quantum simulation, error mitigation technique, quantum machine learning, and quantum optimization, which are explained with illustrations.

John Watrous

Supanut Thanasilp, Jirawat Tangpanitanon, Marc-Antoine Lemonde +2 more

Demonstrating the ability of existing quantum platforms to perform certain computational tasks intractable to classical computers represents a cornerstone in quantum computing. Despite the growing number of such proposed ``quantum supreme'' tasks, it remains an important challenge to identify their direct applications. In this work, we describe how the approach proposed by Tangpanitanon et al. [arXiv:2002.11946] for demonstrating quantum supremacy in generic driven analog many-body systems, such as those found in cold atom and ion setups, can be extended to explore dynamical quantum phase transitions. We show how key quantum supremacy signatures, such as the divergence between the output distribution and the Porter Thomas distribution, can be used as effective order parameters. We apply this approach to a periodically driven disordered one-dimensional Ising model and show that we can accurately capture the transition between the driven thermalized and many-body localized phases. This approach also captures the transition towards the Floquet prethermalized regime for high-frequency driving. Revisiting quantum phases of matter under the light of the recent discussions about quantum supremacy draws a link between complexity theory and analog many-body systems.

Marco O. Lanzagorta, Jeffrey K. Uhlmann