Quantum algorithms and complexity

Quantum algorithms and complexity

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, A/Prof Youming Qiao. A/Prof Troy Lee, Dr Marika Kieferova, Dr Ryan Mann, Dr Luke Mathieson, Mauricio Morales Soler

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.

Selected research outputs

• Quantum Chemistry: ‘Greatly improved higher-order product formulae for quantum simulation’ – research led at UTS by QSI’s Mauro Morales and Dr Yuval Sanders, in collaboration with Macquarie University. 
• Quantum Machine Learning: ‘Generating Approximate Ground States of Molecules Using Quantum Machine Learning’ – Research led at QSI by Dr Marika Kieferova, in collaboration with Xanadu, Berkley and University of Toronto.
• Parametized Complexity: ‘Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis’ – Research led at QSI by Prof Michael Bremner, Prof Zhengfeng Ji, Dr Luke Mathieson and Mauro Morales, in collaboration with Baidu Research. 
• Materials, Simulations and Complexity: ‘Fermion sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states’ – QSI research by Mauro Morales, in collaboration with Center for Theoretical Physics PAS, Laboratory of Quantum Information Science (QIS) and Quantum Computing Research Group, Wigner Research Center for Physics. 
• Materials, Simulations and Complexity: ‘Efficient Algorithms for Approximating Quantum Partition Functions’ – QSI research led by Dr Ryan Mann, in collaboration with Tyler Helmuth at Durham University.
• Simulation of advanced physics models: ‘Entanglement in quantum field theory via wavelet representations’ and ‘Nearly optimal quantum algorithm for generating the ground state of a free quantum field theory’ – QSI research led by Dr Yuval Sanders, in collaboration with Macquarie University, University of Toronto and Institute for Quantum Science and Technology at the University of Calgary.
• Query Complexity: ‘Cut query algorithms with star contraction’ – QSI research led by A/Prof Troy Lee, in collaboration with CNRS IRIF Paris, Columbia University, University of Wroclaw, University of Sheffield and Max Planck Institute for Informatics at the University of Copenhagen. 
• Combinatorics and quantum information: “Connections between graphs and matrix spaces”, “On linear-algebraic notions of expansion”: research led at QSI by A/Prof Youming Qiao and Chuanqi Zhang, with QSI alumni Yinan Li, in collaboration with Institute for Advanced Study at Princeton, and Tel Aviv University.
• Post-quantum cryptography: “Practical Post-Quantum Signature Schemes from Isomorphism Problems of Trilinear Forms”, “On digital signatures based on isomorphism problems: QROM security, ring signatures, and applications”, and a submission to NIST call for post-quantum digital signature schemes ALTEQ: research led at QSI by A/Prof Youming Qiao, Gang Tang, Zhili Chen, in collaboration with Saarland University, CISPA Helmholtz Center for Information Security, University of Wollongong, SandboxAQ, Nokia Bell Labs, KDDI Research.
• Complexity and quantum information: “On the complexity of isomorphism problems for tensors, groups, and polynomials”, parts I, II, and III: research led at QSI by A/Prof Youming Qiao, in collaboration with Colorado University, Boulder, and part III with QSI’s Zhili Chen, Gang Tang, and Chuanqi Zhang