Ashley Montanaro's research

Here are some of my papers and talks. For teaching and other info, click here.

This list might not be up to date; you can also find me on the arXiv or my Google Scholar page.

Publications and preprints

TitleWithReferenceTalks etc.
Pretty simple bounds on quantum state discriminationarXiv:1908.08312
Quantum speedup of branch-and-bound algorithmsarXiv:1906.10375
Quantum sketching protocols for Hamming distance and beyondJočo DoriguelloPhys. Rev. A 99, 062331 (2019)
Computational complexity, step by stepScience 362 (6412), 289
Perspective on "Quantum advantage with shallow circuits"
Applying quantum algorithms to constraint satisfaction problemsEarl Campbell and Ankur KhuranaQuantum 3, 167 (2019)
Universal qudit HamiltoniansStephen PiddockarXiv:1802.07130
Optimal verification of entangled states with local measurementsSam Pallister and Noah LindenPhys. Rev. Lett. 120, 170502 (2018)
Quantum computational supremacyAram HarrowNature 549, 203-209 (2017)
Learning stabilizer states by Bell samplingarXiv:1707.04012Coogee workshop, Sydney, January 2013
IQC colloquium, Waterloo, March 2013
Bristol seminar, March 2013)
The Quantum Complexity of Computing Schatten p-normsChris CadeIn Proc. 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)
Classical boson sampling algorithms with superior performance to near-term experimentsAlex Neville, Chris Sparrow, RaphaŽl Clifford, Eric Johnston, Patrick M. Birchall and Anthony LaingNature Physics (2017)
Quantum key search with side channel adviceDan Martin, Elisabeth Oswald and Dan ShepherdIn Proc. SAC'17
Cryptology ePrint Archive: Report 2017/171
Generating entanglement with linear opticsStasja Stanisic, Noah Linden and Peter TurnerPhys. Rev. A 96, 043861 (2017)
Universal Quantum HamiltoniansToby Cubitt and Stephen PiddockProc. Natl. Acad. Sci. 115:38 p9497-9502 (2018)
Quantum states cannot be transmitted efficiently classicallyQuantum 3, 154 (2019)
Quantum speedup of the Travelling Salesman Problem for bounded-degree graphsDominic Moylett and Noah LindenPhys. Rev. A 95, 032323 (2017)
Achieving quantum supremacy with sparse and noisy commuting quantum circuitsMichael Bremner and Dan ShepherdQuantum 1, 8 (2017)
Time and space efficient quantum algorithms for detecting cycles and testing bipartitenessChris Cade and Alexandrs BelovsarXiv:1610.00581
Quantum circuits and low-degree polynomials over F_2 Journal of Physics A, vol. 50, no. 8, 084002, 2017 (invited special issue: Emerging Talents)
Sequential measurements, disturbance and property testingAram Harrow and Cedric Yen-Yu LinIn Proc. SODA'17, pp. 1598-1611, 2017
SODA, Jan 2017
Quantum algorithms and the finite element methodSam PallisterPhysical Review A vol. 93, 032324, 2016
Quantum algorithms: an overviewnpj Quantum Information vol. 2, 15023, 2016
Efficient quantum walk on a quantum processorXiaogang Qiang, Thomas Loke, Kanin Aungskunsiri, Xiaoqi Zhou, Jeremy L. O'Brien, Jingbo Wang and Jonathan C. F. MatthewsNature Communications 7, article number: 11511 (2016)
Quantum walk speedup of backtracking algorithmsarXiv:1509.02374QALGO workshop, Riga, Sep 2015
Quantum random walks and quantum algorithms workshop, Leiden, Dec 2015
Extremal eigenvalues of local HamiltoniansAram HarrowQuantum 1, 6 (2017)
The complexity of antiferromagnetic interactions and 2D latticesStephen PiddockQuantum Information & Computation vol. 17 no. 7&8, pp. 636-672, 2017
The quantum complexity of approximating the frequency momentsQuantum Information & Computation vol. 16 no. 13&14, pp. 1169-1190, 2016
Average-case complexity versus approximate simulation of commuting quantum computationsMichael Bremner and Dan ShepherdPhysical Review Letters vol. 117, 080501, 2016
Quantum speedup of Monte Carlo methodsProc. Roy. Soc. Ser. A, vol. 471 no. 2181, 20150301, 2015
CEQIP Telc, June 2015
AQIS Seoul, August 2015
Quantum reverse hypercontractivityToby Cubitt, Michael Kastoryano and Kristan TemmeJournal of Mathematical Physics vol. 56 no. 10, 102204, 2015
Quantum pattern matching fast on averageAlgorithmica vol. 77 no. 1, pp. 16-39 (2017)
Complexity classification of local Hamiltonian problemsToby CubittSIAM Journal on Computing vol. 45 no. 2, pp. 268-316, 2016
In Proc. FOCS'14, pp. 120-129, 2014
QIP Barcelona, Feb 2014
Oxford, Jan 2014
Cambridge, Nov 2013
A survey of quantum property testingRonald de WolfTheory of Computing Graduate Surveys 7 (2016)
A composition theorem for decision tree complexityChicago Journal of Theoretical Computer Science, vol. 2014 no. 6, 2014
Quantum algorithms for search with wildcards and combinatorial group testingAndris AmbainisQuantum Information & Computation, vol. 14 no. 5&6, pp. 439-453, 2014
Almost all decision trees do not allow significant quantum speed-upChicago Journal of Theoretical Computer Science vol. 2012
Some applications of hypercontractive inequalities in quantum information theoryJournal of Mathematical Physics, vol. 53, 122206, 2012
Madrid, Jun 2013
Riga, Aug 2013
Weak multiplicativity for random quantum channelsCommunications in Mathematical Physics, vol. 319 no. 2, pp. 535-555, 2013
QIP Beijing, Jan 2013
Marseille, Jan 2012
On exact quantum query complexityRichard Jozsa and Graeme MitchisonAlgorithmica, vol. 71 no. 4, pp. 775-796, 2015
Royal Holloway, Dec 2011
Poster, QIP'12, Dec 2011
Source code
The quantum query complexity of learning multilinear polynomialsInformation Processing Letters, vol. 112, no. 11, pp. 438-442, 2012
Limitations on quantum dimensionality reductionAram W. Harrow and Anthony J. ShortIn Proc. ICALP'11, pp. 86-97, 2011
ICALP, July 2011
A new exponential separation between quantum and classical one-way communication complexityQuantum Information & Computation, vol. 11 no. 7&8, pp. 574-591, 2011
Bristol, Mar 2011
COQUIT workshop, Nov 2010
The complexity of flood filling gamesDavid Arthur, Raphaël Clifford, Markus Jalsenius and Benjamin SachTheory of Computing Systems, vol. 50, no. 1, pp. 72-92, 2012
Preliminary version in Proc. FUN'10
Press release
Slashdot story
Nonadaptive quantum query complexityInformation Processing Letters, vol. 110, no. 24, pp. 1110-1113, 2010
Testing product states, quantum Merlin-Arthur games and tensor optimisationAram W. HarrowJournal of the ACM, vol. 60 no. 1, 2013
Previous version in Proc. FOCS'10
QIP Singapore, Jan 2011
Heilbronn Quantum Algorithms Day, May 2010
On the communication complexity of XOR functionsTobias OsbornearXiv:0909.3392National University of Singapore, Oct 2009
Quantum search with adviceIn Proc. TQC'10
Departmental seminar
Symmetric functions of qubits in an unknown basisPhys. Rev. A 79, 062316, 2009
Quantum boolean functionsTobias OsborneChicago Journal of Theoretical Computer Science 2010
Perimeter Institute, Dec 2008
Quantum algorithms for shifted subset problemsQuantum Information & Computation vol. 9 no. 5&6, pp. 500-512, 2009
AQIS'08, Aug 2008
Structure, randomness and complexity in quantum computationPhD thesis
Counterexamples to additivity of minimum output p-Renyi entropy for p close to 0Toby Cubitt, Aram W. Harrow, Debbie Leung and Andreas WinterCommunications in Mathematical Physics vol. 284 pp. 281-290, 2008
Unbounded error quantum query complexityHarumichi Nishimura and Rudy RaymondIn Proc. ISAAC'08
Poster, QICS workshop, September 2008
A lower bound on the probability of error in quantum state discriminationIn Proc. IEEE Information Theory Workshop 2008
IEEE Information Theory Workshop 2008
On the dimension of subspaces with bounded Schmidt rankToby Cubitt and Andreas WinterJournal of Mathematical Physics 49, 022107, 2008
Quantum search of partially ordered setsQuantum Information & Computation, vol. 9, no. 7&8, pp. 0628-0647, 2009
Short talk, Bristol Algorithms Day 2008
Poster, QIP'08, Dec 2007
Long talk, Feb 2007
A lower bound on entanglement-assisted quantum communication complexityAndreas WinterIn Proc. ICALP'07
Hadamard gates and amplitudes of computational basis statesDan Shepherd
On the quantum chromatic number of a graphPeter Cameron, Mike Newman, Simone Severini and Andreas WinterElectronic Journal of Combinatorics vol. 14 no. 1, 2007
On the distinguishability of random quantum statesCommunications in Mathematical Physics vol. 273 no. 3, pp. 619-636, 2007
Long talk, Oct 2006
Short talk, Sep 2006
Quantum walks on directed graphsQuantum Information & Computation vol. 7 no. 1, pp. 93-102, 2007
Poster, QIP'06, Jan 2006

Other presentations

Here are some other presentations I've given.