Markovian quantum algorithm for combinatorial optimization
ABSTRACT :
Quantum computers are often portrayed rather wrongly in public as exceptionally mighty devices, capable of executing any calculations at unprecedented speed. However, the full extent of potential and limitations of quantum computation is yet to be understood. While the potential remains somewhat elusive, the identified constraints are restrictive and universal, making the development of quantum algorithms a complicated and ad hoc process. This talk begins with a brief introduction to complexity theory and quantum algorithms. It is possible to formulate a general representation of computationally hard problems in classical computers, the solutions to which are the essential driving force behind the pursuit of quantum computers. However, conceivable universal quantum approaches fail to achieve a substantial speedup. We discuss the reasons underpinning this limitation. I then introduce a new framework to address similar problems, which are based on the working principle of many-body cooling. While this approach initially seems promising, it encounters a comparable limitation. This realization, on one hand, strengthens our pessimism concerning the practical usefulness of quantum computers. On the other hand, the new approach brings a number of advantages, which may prove to be useful in some significant calculations.
ABOUT THE SPEAKER:
Jaeyoon Cho is an assistant professor in the Department of Physics at Gyeongsang National University, Korea. He obtained his PhD in quantum information theory and quantum optics from Korea Advanced Institute of Science and Technology in 2005. Since then, he has worked at various institutes including KRISS, University College London, Queen's Univerisy Belfast, Imperial College London, KIAS, and APCTP and on a broad range of theoretical topics within physics and mathematics, pertaining to quantum information theory.