Advancing our knowledge of quantum computation by enriching the quantum algorithm toolbox and bridging computational complexity theory techniques.
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?”.
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.
Chen, J, Ji, Z, Kribs, DW, Zeng, B & Zhang, F 2019, 'Minimum entangling power is close to its maximum', Journal of Physics A: Mathematical and Theoretical, vol. 52, no.21. View/Download from: UTS OPUS or Publisher's site
Halasi, Z, Maróti, A, Pyber, L & Qiao, Y 2019, 'An improved diameter bound for finite simple groups of Lie type', Bulletin of the London Mathematical Society, vol. 51, no. 4, pp. 645-657. View/Download from: UTS OPUS or Publisher's site
Ivanyos, G & Qiao, Y 2019, 'Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing', SIAM Journal on Computing, vol. 48, no. 3, pp. 926-963. View/Download from: UTS OPUS or Publisher's site
Li, Y, Lei, L & Li, S 2019, 'Computation tree logic model checking based on multi-valued possibility measures', Information Sciences, vol. 485, pp. 87 113. View/Download from: UTS OPUS or Publisher's site
Zhou, X, Li, S & Feng, Y 2020, 'Quantum Circuit Transformation Based on Simulated Annealing and Heuristic Search', IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. View/Download from: UTS OPUS or Publisher's site
Qiao, Y, Ji, Z, Yun, A & Song, F 2019, 'General Linear Group Action on Tensors: A Candidate for Post-quantum Cryptography', Theory of Cryptography - 17th International Conference, Nuremberg.View/Download from: UTS OPUS or Publisher's site
Fitzsimons, J, Ji, Z, Vidick, T & Yuen, H 2019, 'Quantum proof systems for iterated exponential time, and beyond', Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 473-480.View/Download from: UTS OPUS or Publisher's site