**Title** | **With** | **Reference** | **Talks etc.** |

Quantum walk speedup of backtracking algorithms | | arXiv:1509.02374 | QALGO workshop, Riga, Sep 2015 |

Extremal eigenvalues of local Hamiltonians | Aram Harrow | arXiv:1507.00739 | |

The complexity of antiferromagnetic interactions and 2D lattices | Stephen Piddock | arXiv:1506.04014 | |

The quantum complexity of approximating the frequency moments | | arXiv:1505.00113 | |

Average-case complexity versus approximate simulation of commuting quantum computations | Michael Bremner and Dan Shepherd | arXiv:1504.07999 | |

Quantum speedup of Monte Carlo methods | | *Proc. Roy. Soc. Ser. A*, vol. 471 no. 2181, 20150301, 2015 arXiv:1504.06987 | CEQIP Telc, June 2015 AQIS Seoul, August 2015 |

Quantum reverse hypercontractivity | Toby Cubitt, Michael Kastoryano and Kristan Temme | arXiv:1504.06143 | |

Quantum pattern matching fast on average | | *Algorithmica*, to appear arXiv:1408.1816 | |

Complexity classification of local Hamiltonian problems | Toby Cubitt | In *Proc. FOCS'14*, pp. 120-129, 2014 arXiv:1311.3161 | QIP Barcelona, Feb 2014 Oxford, Jan 2014 Cambridge, Nov 2013 |

A survey of quantum property testing | Ronald de Wolf | *Theory of Computing Graduate Surveys*, to appear arXiv:1310.2035 | |

A composition
theorem for decision tree complexity | | *Chicago Journal of Theoretical Computer Science*, vol. 2014 no. 6, 2014 arXiv:1302.4207 | |

Quantum algorithms for
search with wildcards and combinatorial group testing | Andris Ambainis | *Quantum Information & Computation*, vol. 14 no. 5&6, pp. 439-453, 2014 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 | Madrid, Jun 2013 Riga, Aug 2013 |

Weak multiplicativity
for random quantum
channels | | *Communications 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
complexity | Richard Jozsa and Graeme
Mitchison | *Algorithmica*, vol. 71 no. 4, pp. 775-796, 2013 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 |