Ashley Montanaro's homepage

As of August 2010, I have moved to the Centre for Quantum Information and Foundations at DAMTP, at the University of Cambridge.
This website will probably not be kept up to date.

I'm an EPSRC postdoctoral research fellow in the Quantum Computation and Information group at the University of Bristol.

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 new exponential separation between quantum and classical one-way communication complexity		arXiv:1007.3587
The complexity of flood filling games	David Arthur, Raphaël Clifford, Markus Jalsenius and Benjamin Sach	In Proc. FUN'10 arXiv:1001.4420	Press release Slashdot story
Nonadaptive quantum query complexity		arXiv:1001.0018
An efficient test for product states, with applications to quantum Merlin-Arthur games	Aram Harrow	In Proc. FOCS'10 arXiv:1001.0017	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, to appear 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 (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.

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)
Quantum walks: definition and applications (May 2005)
Classical and quantum algorithms for Boolean satisfiability (April 2005)

Other

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.
I've written some brief notes about Razborov and Rudich's "Natural Proofs".
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

You can e-mail me using a web form. Alternatively, my email address is (the first eight letters of my surname) at cs.bris.ac.uk. Click here for more contact information.