| Title | With | Reference | Talks etc. | |
| Pretty simple bounds on quantum state discrimination | arXiv:1908.08312 | |||
| Quantum speedup of branch-and-bound algorithms | arXiv:1906.10375 | |||
| Quantum sketching protocols for Hamming distance and beyond | Jo‹o Doriguello | Phys. Rev. A 99, 062331 (2019) arXiv:1810.12808 | ||
| Computational complexity, step by step | Science 362 (6412), 289 Perspective on "Quantum advantage with shallow circuits" | |||
| Applying quantum algorithms to constraint satisfaction problems | Earl Campbell and Ankur Khurana | Quantum 3, 167 (2019) arXiv:1810.05582 | ||
| Universal qudit Hamiltonians | Stephen Piddock | arXiv:1802.07130 | ||
| Optimal verification of entangled states with local measurements | Sam Pallister and Noah Linden | Phys. Rev. Lett. 120, 170502 (2018) arXiv:1709.03353 | ||
| Quantum computational supremacy | Aram Harrow | Nature 549, 203-209 (2017) | ||
| Learning stabilizer states by Bell sampling | arXiv:1707.04012 | Coogee workshop, Sydney,
January 2013 IQC colloquium, Waterloo, March 2013 Bristol seminar, March 2013) | ||
| The Quantum Complexity of Computing Schatten p-norms | Chris Cade | In Proc. 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018) arXiv:1706.09279 | ||
| Classical boson sampling algorithms with superior performance to near-term experiments | Alex Neville, Chris Sparrow, Raphaël Clifford, Eric Johnston, Patrick M. Birchall and Anthony Laing | Nature Physics (2017) arXiv:1705.00686 | ||
| Quantum key search with side channel advice | Dan Martin, Elisabeth Oswald and Dan Shepherd | In Proc. SAC'17 Cryptology ePrint Archive: Report 2017/171 | ||
| Generating entanglement with linear optics | Stasja Stanisic, Noah Linden and Peter Turner | Phys. Rev. A 96, 043861 (2017) arXiv:1701.05289 | ||
| Universal Quantum Hamiltonians | Toby Cubitt and Stephen Piddock | Proc. Natl. Acad. Sci. 115:38 p9497-9502 (2018) arXiv:1701.05182 | ||
| Quantum states cannot be transmitted efficiently classically | Quantum 3, 154 (2019) arXiv:1612.06546 | |||
| Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs | Dominic Moylett and Noah Linden | Phys. Rev. A 95, 032323 (2017) arXiv:1612.06203 | ||
| Achieving quantum supremacy with sparse and noisy commuting quantum circuits | Michael Bremner and Dan Shepherd | Quantum 1, 8 (2017) arXiv:1610.01808 | ||
| Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness | Chris Cade and Alexandrs Belovs | arXiv:1610.00581 | ||
| Quantum circuits and low-degree polynomials over F_2 |
Journal of Physics A, vol. 50, no. 8, 084002, 2017 (invited special issue: Emerging Talents) arXiv:1607.08473 | |||
| Sequential measurements, disturbance and property testing | Aram Harrow and Cedric Yen-Yu Lin | In Proc. SODA'17, pp. 1598-1611, 2017 arXiv:1607.03236 | SODA, Jan 2017 | |
| Quantum algorithms and the finite element method | Sam Pallister | Physical Review A vol. 93, 032324, 2016 arXiv:1512.05903 | ||
| Quantum algorithms: an overview | npj Quantum Information vol. 2, 15023, 2016 arXiv:1511.04206 | |||
| Efficient quantum walk on a quantum processor | Xiaogang Qiang, Thomas Loke, Kanin Aungskunsiri, Xiaoqi Zhou, Jeremy L. O'Brien, Jingbo Wang and Jonathan C. F. Matthews | Nature Communications 7,
article number: 11511 (2016) arXiv:1510.08657 | ||
| Quantum walk speedup of backtracking algorithms | arXiv:1509.02374 | QALGO
workshop, Riga, Sep
2015 Quantum random walks and quantum algorithms workshop, Leiden, Dec 2015 | ||
| Extremal eigenvalues of local Hamiltonians | Aram Harrow | Quantum 1, 6 (2017) arXiv:1507.00739 | ||
| The complexity of antiferromagnetic interactions and 2D lattices | Stephen Piddock | Quantum Information & Computation vol. 17 no. 7&8, pp. 636-672, 2017 arXiv:1506.04014 | ||
| The quantum complexity of approximating the frequency moments | Quantum Information & Computation vol. 16 no. 13&14, pp. 1169-1190, 2016 arXiv:1505.00113 | |||
| Average-case complexity versus approximate simulation of commuting quantum computations | Michael Bremner and Dan Shepherd | Physical Review Letters vol. 117, 080501, 2016 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 | Journal of Mathematical Physics vol. 56
no. 10, 102204, 2015 arXiv:1504.06143 | ||
| Quantum pattern matching fast on average | Algorithmica vol. 77 no. 1, pp. 16-39 (2017) arXiv:1408.1816 | |||
| Complexity classification of local Hamiltonian problems | Toby Cubitt | SIAM Journal on Computing vol. 45 no. 2, pp. 268-316, 2016 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 7 (2016) 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, 2015 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 |