Title | With | Reference | Talks etc. |

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 | arXiv:1504.06987 | CEQIP Telc, June 2015 | |

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

Quantum pattern matching fast on average | arXiv:1408.1816 | ||

Complexity classification of local Hamiltonian problems | Toby Cubitt | In Proc. FOCS'14, pp. 120-129, 2014arXiv: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 appeararXiv:1310.2035 | |

A composition theorem for decision tree complexity | Chicago Journal of Theoretical Computer Science, vol. 2014 no. 6, 2014arXiv: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, 2014arXiv:1210.1148 | |

Almost all decision trees do not allow significant quantum speed-up | Chicago
Journal of Theoretical Computer Science vol. 2012arXiv:1209.4781 | ||

Some applications of hypercontractive inequalities in quantum information theory | Journal of Mathematical Physics,
vol. 53, 122206, 2012arXiv: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, 2013arXiv: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, 2013arXiv: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, 2012arXiv:1105.3310 | ||

Limitations on quantum dimensionality reduction | Aram W. Harrow and Anthony J. Short | In Proc. ICALP'11, pp. 86-97, 2011arXiv: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, 2011arXiv: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, 2012Preliminary version in Proc. FUN'10arXiv:1001.4420 | Press release Slashdot story |

Nonadaptive quantum query complexity | Information Processing Letters, vol. 110, no. 24, pp. 1110-1113, 2010arXiv:1001.0018 | ||

Testing product states, quantum Merlin-Arthur games and tensor optimisation | Aram W. Harrow | Journal of the
ACM, vol. 60 no. 1, 2013Previous version in Proc. FOCS'10arXiv: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'10arXiv:0908.3066 | Departmental seminar | |

Symmetric functions of qubits in an unknown basis | Phys. Rev. A 79, 062316, 2009arXiv:0903.5466 | ||

Quantum boolean functions | Tobias Osborne | Chicago Journal of Theoretical Computer Science 2010arXiv:0810.2435 | Perimeter Institute, Dec 2008 |

Quantum algorithms for shifted subset problems | Quantum Information & Computation vol. 9 no. 5&6, pp. 500-512, 2009arXiv: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, 2008arXiv:0712.3628 | |

Unbounded error quantum query complexity | Harumichi Nishimura and Rudy Raymond | In Proc. ISAAC'08arXiv: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 2008arXiv: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, 2008arXiv:0706.0705 | |

Quantum search of partially ordered sets | Quantum Information & Computation, vol. 9, no. 7&8, pp. 0628-0647, 2009quant-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'07quant-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, 2007quant-ph/0608016 | |

On the distinguishability of random quantum states | Communications in Mathematical Physics vol. 273 no. 3, pp. 619-636, 2007quant-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, 2007quant-ph/0504116 | Poster, QIP'06, Jan 2006 |

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

- Applications of hypercontractivity in quantum information (Banff workshop, February 2015)
- Quantum Algorithms (Southwest Quantum Technologies workshop, February 2015)
- Combinatorics in quantum computation, and vice versa (Combinatorics group seminar, Bristol, December 2014)
- Mathematical Challenges in Quantum Algorithms (Turing Gateway workshop on post-quantum research, September 2014)
- The Power of Quantum Computation (Turing Gateway workshop on post-quantum research, May 2014)
- Quantum Computing Applications (DSTL Bristol Quantum Information Technologies Workshop, February 2014)
- Quantum Computing (Bristol UCAS day)
- Hypercontractivity, XOR games and the Aaronson-Ambainis conjecture (Riga, August 2013)
- A brief overview of some recent quantum algorithms (QCS/QALGO workshop, Paris, May 2013)
- 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)

- 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.