1.1k citations · 4.7k across the 73 of their papers we have counts for
5 papers · 2 filters
Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs
Alexandra E. Moylett, Noah Linden, Ashley Montanaro
The Travelling Salesman Problem is one of the most famous problems in graph theory. However, little is currently known about the extent to which quantum computers could speed up al…
Quantum states cannot be transmitted efficiently classically
Ashley Montanaro
We show that any classical two-way communication protocol with shared randomness that can approximately simulate the result of applying an arbitrary measurement (held by one party)…
Time and Space Efficient Quantum Algorithms for Detecting Cycles and Testing Bipartiteness
Chris Cade, Ashley Montanaro, Aleksandrs Belovs
We study space and time efficient quantum algorithms for two graph problems -- deciding whether an -vertex graph is a forest, and whether it is bipartite. Via a reduction to the…
Achieving quantum supremacy with sparse and noisy commuting quantum computations
Michael J. Bremner, Ashley Montanaro, Dan J. Shepherd
The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoreti…
Sequential measurements, disturbance and property testing
Aram W. Harrow, Cedric Yen-Yu Lin, Ashley Montanaro
We describe two procedures which, given access to one copy of a quantum state and a sequence of two-outcome measurements, can distinguish between the case that at least one of the…