Supra-classical quantum simulation in physically restricted models of quantum computation

Funding: 2011: $157,576
2012: $141,132
2013: $143,576
2014: $141,132

Funding or Partner Organisation: Australian Research Council (ARC Future Fellowships)
University of Cambridge
University of Washington - Seattle (University of Washington, Seattle)

Start year: 2012

Summary: The resource savings potentially offered by Quantum Computation are driving remarkable advancements in theoretical and experimental physics, mathematics and computer science. These expectations are tempered by the lack of rigorous proof of the superiority of quantum computers and the considerable experimental challenges to be overcome. This project addresses these concerns through the development of quantum simulation algorithms that are supra-classical, given that the Polynomial Hierarchy has infinite extent. Furthermore, these algorithms can be performed by physically simple forms of quantum computers. This project poses the most significant challenge to the Extended Church-Turing Thesis since the advent of Shor's acclaimed algorithm.

Publications:

Lund, AP, Bremner, MJ & Ralph, TC 2017, 'Quantum Sampling Problems, BosonSampling and Quantum Supremacy', npj Quantum Information (2017) 3:15, vol. 3, no. 1, pp. 1-8.
View/Download from: Publisher's site

Boixo, S, Isakov, SV, Smelyanskiy, VN, Babbush, R, Ding, N, Jiang, Z, Bremner, MJ, Martinis, JM & Neven, H 2016, 'Characterizing Quantum Supremacy in Near-Term Devices', Nature Physics, vol. 14, no. 6, pp. 595-600.
View/Download from: Publisher's site

Bremner, MJ, Montanaro, A & Shepherd, DJ 2016, 'Achieving quantum supremacy with sparse and noisy commuting quantum computations', Quantum, vol. 1, pp. 8-8.
View/Download from: Publisher's site

Bremner, MJ, Montanaro, A & Shepherd, DJ 2016, 'Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations', PHYSICAL REVIEW LETTERS, vol. 117, no. 8.
View/Download from: Publisher's site

Bremner, MJ, Montanaro, A & Shepherd, D 1970, 'Average-case complexity versus approximate simulation of commuting quantum computations', 19th Conference on Quantum Information Processing, Banff, Canada.

Bremner, MJ, Montanaro, A & Shepherd, D 1970, 'Average-case complexity versus approximate simulation of commuting quantum computations', 15th Asian Quantum Information Science Conference, Seoul, Korea.

Keywords: Quantum computation;Quantum computational complexity;Quantum algorithms

FOR Codes: Mathematical Aspects of Classical Mechanics, Quantum Mechanics and Quantum Information Theory, Expanding Knowledge in the Mathematical Sciences, Quantum Information, Computation and Communication, Expanding Knowledge in the Physical Sciences, Analysis of Algorithms and Complexity, Expanding Knowledge in the Information and Computing Sciences, Mathematical aspects of classical mechanics, quantum mechanics and quantum information theory, Quantum information, computation and communication, Computational complexity and computability

Acknowledgement of Country

UTS acknowledges the Gadigal people of the Eora Nation, the Boorooberongal people of the Dharug Nation, the Bidiagal people and the Gamaygal people, upon whose ancestral lands our university stands. We would also like to pay respect to the Elders both past and present, acknowledging them as the traditional custodians of knowledge for these lands.