The forthcoming quantum leap in information technology depends essentially on our improved understanding of quantum algorithms and complexity. The aim of this research program at QSI is to advance our knowledge of quantum computation, by enriching the quantum algorithm toolbox and by bridging computational complexity theory techniques with the unique features of quantum computation. Important questions in the area include: "Can we harness the power of quantum mechanics in solving real-world problems?", "How to enrich the quantum algorithm toolbox and develop new designing methodologies and frameworks", and "What are the ultimate limitations of quantum computing?”.
Key Members: Prof Michael Bremner, Prof Sanjiang Li, and Dr Youming Qiao
Quantum algorithms and real-world applications
Good quantum algorithms are notoriously hard to design. Several methodologies such as the quantum Fourier transform, phase estimation, amplitude amplification, quantum walks and Hamiltonian simulation form a basic toolbox that provides viable approaches to the designing of quantum algorithms. One of our fundamental research problems is to better understand these existing methodologies and, more importantly, to come up with completely new frameworks that can assist the design of quantum algorithms, and to find broader applications of quantum algorithms to real-world problems in artificial intelligence, machine learning, big data science, approximation algorithms, and optimisation.
Quantum complexity theory
Even though quantum computers are believed to be a much more powerful model than classical computers, they have their own limitations. Exploring the limits of quantum computing in different models, finding how they relate to classical complexity classes, and characterising the boundary of efficient quantum computation, provide deeper understanding of quantum computation. Research in this direction also has interesting applications to verifications of quantum computation, delegations of quantum computing and post-quantum cryptography.
We also investigate complexity problems arising from the analysis of near-term quantum devices and blue-sky research problems related to quantum computing, such as the group isomorphism and polynomial identity testing problems.
- Zhengfeng Ji. Compression of quantum multi-prover interactive proofs. QIP 2017.
- Zhengfeng Ji. Classical verification of quantum proofs. STOC 2016 (Earlier version: QIP 2016).
- Anne Broadbent, Zhengfeng Ji, Fang Song, and John Watrous. Zero-knowledge proof systems for QMA. FOCS 2016 (also QIP 2017).
- Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao. Boundaries of VP and VNP. ICALP 2016.
- Thomas Decker, Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, and Miklos Santha. An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group. MFCS 2014.
- Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous. QIP = PSPACE. J. ACM (2011) (STOC 2010 Best Paper Award; QIP 2010 plenary talk).