Ashley Montanaro's homepage

In June 2013 I will be moving to the Computer Science department at the University of Bristol. This page will probably not be kept up to date.

I'm a postdoctoral research associate in the Centre for Quantum Information and Foundations at the University of Cambridge.

I taught the Part III course Computational Complexity in Michaelmas term 2012. Click on the link for lecture notes and examples sheets.

Research interests

I'm interested in all areas of quantum computation, but particularly quantum algorithms, quantum query and communication complexity, quantum measurement and state discrimination, and quantum walks. I also have a strong interest in the Fourier analysis of boolean functions.

Publications and preprints

TitleWithReferenceTalks etc.
A composition theorem for decision tree complexityarXiv:1302.4207
Quantum algorithms for search with wildcards and combinatorial group testingAndris AmbainisarXiv:1210.1148
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)
Weak multiplicativity for random quantum channelsCommunications in Mathematical Physics, to appear
QIP Beijing, Jan 13
Marseille, Jan 12
On exact quantum query complexityRichard Jozsa and Graeme MitchisonarXiv:1111.0475Royal 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

Or you can search the arXiv for my stuff.


Miscellaneous presentations

Here are some other presentations I've given.




My email address is am994 (at)