Ashley Montanaro's research

Here are some details about my research. For teaching and other info, click here.

Publications and preprints

TitleWithReferenceTalks etc.
Quantum pattern matching fast on averagearXiv:1408.1816
Complexity classification of local Hamiltonian problemsToby CubittIn Proc. FOCS'14, to appear
arXiv:1311.3161
QIP Barcelona, Feb 2014
Oxford, Jan 2014
Cambridge, Nov 2013
A survey of quantum property testingRonald de WolfarXiv:1310.2035
A composition theorem for decision tree complexityChicago Journal of Theoretical Computer Science, vol. 2014 no. 6, 2014
arXiv:1302.4207
Quantum algorithms for search with wildcards and combinatorial group testingAndris AmbainisQuantum Information & Computation, vol. 14 no. 5&6, pp. 439-453, 2014
arXiv:1210.1148
Almost all decision trees do not allow significant quantum speed-upChicago Journal of Theoretical Computer Science vol. 2012
arXiv:1209.4781
Some applications of hypercontractive inequalities in quantum information theoryJournal of Mathematical Physics, vol. 53, 122206, 2012
arXiv:1208.0161
Madrid, Jun 2013
Riga, Aug 2013
Weak multiplicativity for random quantum channelsCommunications in Mathematical Physics, vol. 319 no. 2, pp. 535-555, 2013
arXiv:1112.5271
QIP Beijing, Jan 2013
Marseille, Jan 2012
On exact quantum query complexityRichard Jozsa and Graeme MitchisonAlgorithmica, to appear
arXiv:1111.0475
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
arXiv:1105.3310
Limitations on quantum dimensionality reductionAram W. Harrow and Anthony J. ShortIn Proc. ICALP'11, pp. 86-97, 2011
arXiv:1012.2262
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
arXiv:1007.3587
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
arXiv:1001.4420
Press release
Slashdot story
Nonadaptive quantum query complexityInformation Processing Letters, vol. 110, no. 24, pp. 1110-1113, 2010
arXiv:1001.0018
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
arXiv:1001.0017
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
arXiv:0908.3066
Departmental seminar
Symmetric functions of qubits in an unknown basisPhys. Rev. A 79, 062316, 2009
arXiv:0903.5466
Quantum boolean functionsTobias OsborneChicago Journal of Theoretical Computer Science 2010
arXiv:0810.2435
Perimeter Institute, Dec 2008
Quantum algorithms for shifted subset problemsQuantum Information & Computation vol. 9 no. 5&6, pp. 500-512, 2009
arXiv:0806.3362
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
arXiv:0712.3628
Unbounded error quantum query complexityHarumichi Nishimura and Rudy RaymondIn Proc. ISAAC'08
arXiv:0712.1446
Poster, QICS workshop, September 2008
A lower bound on the probability of error in quantum state discriminationIn Proc. IEEE Information Theory Workshop 2008
arXiv:0711.2012
IEEE Information Theory Workshop 2008
On the dimension of subspaces with bounded Schmidt rankToby Cubitt and Andreas WinterJournal of Mathematical Physics 49, 022107, 2008
arXiv:0706.0705
Quantum search of partially ordered setsQuantum Information & Computation, vol. 9, no. 7&8, pp. 0628-0647, 2009
quant-ph/0702196
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
quant-ph/0610085
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
quant-ph/0608016
On the distinguishability of random quantum statesCommunications in Mathematical Physics vol. 273 no. 3, pp. 619-636, 2007
quant-ph/0607011
Long talk, Oct 2006
Short talk, Sep 2006
Quantum walks on directed graphsQuantum Information & Computation vol. 7 no. 1, pp. 93-102, 2007
quant-ph/0504116
Poster, QIP'06, Jan 2006

You can also find me on the arXiv or my Google Scholar page.

Other presentations

Here are some other presentations I've given.

Other