Projects per year
Abstract
We use the class of commuting quantum computations known as IQP (Instantaneous Quantum Polynomial time) to strengthen the conjecture that quantum computers are hard to simulate classically. We show that, if either of two plausible averagecase hardness conjectures holds, then IQP computations are hard to simulate classically up to constant additive error. One conjecture elates to the hardness of estimating the complextemperature partition function for random instances of the Ising model; the other concerns approximating the
number of zeroes of random lowdegree polynomials. We observe that both conjectures can be shown to be valid in the setting of worstcase complexity. We arrive at these conjectures by deriving spinbased generalisations of the Boson Sampling problem that avoid the socalled permanent anticoncentration conjecture.
number of zeroes of random lowdegree polynomials. We observe that both conjectures can be shown to be valid in the setting of worstcase complexity. We arrive at these conjectures by deriving spinbased generalisations of the Boson Sampling problem that avoid the socalled permanent anticoncentration conjecture.
Original language  English 

Article number  080501 
Number of pages  5 
Journal  Physical Review Letters 
Volume  117 
DOIs  
Publication status  Published  18 Aug 2016 
Fingerprint
Dive into the research topics of 'Averagecase complexity versus approximate simulation of commuting quantum computations'. Together they form a unique fingerprint.Projects
 2 Finished
Profiles

Professor Ashley M R Montanaro
 School of Mathematics  Professor of Quantum Computation
 The Bristol Centre for Nanoscience and Quantum Information
 Algorithms and Complexity
 Mathematical Physics
 Quantum Information Theory
Person: Academic , Member, Group lead