Ashley Montanaro's homepage

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

Title	With	Reference	Talks etc.
A composition theorem for decision tree complexity		arXiv:1302.4207
Quantum algorithms for search with wildcards and combinatorial group testing	Andris Ambainis	arXiv:1210.1148
Almost all decision trees do not allow significant quantum speed-up		Chicago Journal of Theoretical Computer Science vol. 2012 arXiv:1209.4781
Some applications of hypercontractive inequalities in quantum information theory		Journal of Mathematical Physics, vol. 53, 122206 (2012) arXiv:1208.0161
Weak multiplicativity for random quantum channels		Communications in Mathematical Physics, to appear arXiv:1112.5271	QIP Beijing, Jan 13 Marseille, Jan 12
On exact quantum query complexity	Richard Jozsa and Graeme Mitchison	arXiv:1111.0475	Royal Holloway, Dec 2011 Poster, QIP'12, Dec 2011 Source code
The quantum query complexity of learning multilinear polynomials		Information Processing Letters, vol. 112, no. 11, pp. 438-442, 2012 arXiv:1105.3310
Limitations on quantum dimensionality reduction	Aram W. Harrow and Anthony J. Short	In Proc. ICALP'11, pp. 86-97, 2011 arXiv:1012.2262	ICALP, July 2011
A new exponential separation between quantum and classical one-way communication complexity		Quantum 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 games	David Arthur, Raphaël Clifford, Markus Jalsenius and Benjamin Sach	Theory 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 complexity		Information Processing Letters, vol. 110, no. 24, pp. 1110-1113, 2010 arXiv:1001.0018
Testing product states, quantum Merlin-Arthur games and tensor optimisation	Aram W. Harrow	Journal 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 functions	Tobias Osborne	arXiv:0909.3392	National University of Singapore, Oct 2009
Quantum search with advice		In Proc. TQC'10 arXiv:0908.3066	Departmental seminar
Symmetric functions of qubits in an unknown basis		Phys. Rev. A 79, 062316, 2009 arXiv:0903.5466
Quantum boolean functions	Tobias Osborne	Chicago Journal of Theoretical Computer Science 2010 arXiv:0810.2435	Perimeter Institute, Dec 2008
Quantum algorithms for shifted subset problems		Quantum Information & Computation vol. 9 no. 5&6, pp. 500-512, 2009 arXiv:0806.3362	AQIS'08, Aug 2008
Structure, randomness and complexity in quantum computation		PhD thesis
Counterexamples to additivity of minimum output p-Renyi entropy for p close to 0	Toby Cubitt, Aram W. Harrow, Debbie Leung and Andreas Winter	Communications in Mathematical Physics vol. 284 pp. 281-290, 2008 arXiv:0712.3628
Unbounded error quantum query complexity	Harumichi Nishimura and Rudy Raymond	In Proc. ISAAC'08 arXiv:0712.1446	Poster, QICS workshop, September 2008
A lower bound on the probability of error in quantum state discrimination		In Proc. IEEE Information Theory Workshop 2008 arXiv:0711.2012	IEEE Information Theory Workshop 2008
On the dimension of subspaces with bounded Schmidt rank	Toby Cubitt and Andreas Winter	Journal of Mathematical Physics 49, 022107, 2008 arXiv:0706.0705
Quantum search of partially ordered sets		Quantum 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 complexity	Andreas Winter	In Proc. ICALP'07 quant-ph/0610085
Hadamard gates and amplitudes of computational basis states	Dan Shepherd
On the quantum chromatic number of a graph	Peter Cameron, Mike Newman, Simone Severini and Andreas Winter	Electronic Journal of Combinatorics vol. 14 no. 1, 2007 quant-ph/0608016
On the distinguishability of random quantum states		Communications 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 graphs		Quantum Information & Computation vol. 7 no. 1, pp. 93-102, 2007 quant-ph/0504116	Poster, QIP'06, Jan 2006

Or you can search the arXiv for my stuff.

Teaching

Computational Complexity (Part III, Michaelmas 2012)
Quantum computation lecture notes (v1.11) and exercises (v1.1); also slides about quantum walks (Part III, Michaelmas 2011)
Computational complexity (for BCCS: Computational modelling of complex systems, June 2010)
Counting perfect matchings in planar graphs (guest lecture, Advanced Algorithms, December 2009)
Metric embeddings (guest lecture, Advanced Algorithms, December 2008)

Miscellaneous presentations

Here are some other presentations I've given.

A brief intro to dynamic programming (University of Bristol, January 2013)
Three quantum learning algorithms (talk at Coogee workshop, Sydney, January 2013; at IQC colloquium, Waterloo, March 2013; and at Bristol, March 2013)
The Church-Turing thesis in a quantum world (talk at BMC workshop on Turing's legacy, Kent, April 2012)
Injective tensor norms and open problems in quantum information (seminar, Madrid, January 2012)
Fourier analysis of boolean functions in quantum computation (seminar, Madrid, September 2011)
Counting perfect matchings in planar graphs (guest lecture, Advanced Algorithms, December 2009)
A quantum analogue of Fourier analysis on the boolean cube (invited talk, QIPC, September 2009)
Metric embeddings (guest lecture, Advanced Algorithms, December 2008)

Other

I've written an article titled "Unentangled Quantum Proofs and their Applications" for ERCIM News 85.
Ever wondered how to win a game show with a quantum computer?
Dan Shepherd and I solved the 10th most annoying problem in quantum computation.
It's a little-known fact that Everett's paper introducing the "relative-state" (or "many-worlds") interpretation of quantum mechanics is available online.

Affiliations

Bristol Summer School on Probabilistic Techniques in Computer Science
Theory of Computing reading group ('08)
Theory of Computing reading group ('07)
Quantum information reading group

Contact

My email address is am994 (at) cam.ac.uk.