In work with Aleksandr Arkhipov, we proposed a rudimentary form of quantum computing, based on linear optics with nonadaptive measurements; and used a connection between linear optics and the permanent function to show that even this limited model could solve sampling and search problems that are intractable for classical computers under plausible complexity assumptions. In this talk, I'll discuss this work in a self-contained way, and mention some of its implications for quantum computing experiments.

I'll also discuss some more general results that emerged from our work.

These include a new equivalence between sampling problems and search problems based on Kolmogorov complexity; a new, linear-optics-based proof of Valiant's famous theorem that the permanent is #P-complete; and a new classical approximation algorithm for the permanent.

Papers:

The Computational Complexity of Linear Optics - http://arxiv.org/abs/1011.3245

The Equivalence of Sampling and Searching - http://arxiv.org/abs/1009.5104

A Linear-Optical Proof that the Permanent is #P-Hard - http://www.scottaaronson.com/papers/sharp.pdf

Bell's theorem gives us a clear distinction between quantum and classical resources. This result has been utilised in protocols where communication is a key resource; either making it secure or quantifying the amount needed for communication complexity tasks. Concerning computation (particularly quantum computing), the role of Bell's theorem is not so clear. We summarise recent research that explores connections between a particular model of quantum computing (Measurement-based Quantum Computing) and many-party Bell tests [1]. We will give indications of how to disambiguate quantum from classical computation in terms of computational expressiveness. We will also discuss tentative connections to subjects as varied as sampling complexity [1] and so-called loopholes in Bell tests [2].

The work summarised here was completed at University College London, in collaboration with Dan Browne, Earl Campbell, Klearchos Loukopoulos and Joel Wallman.

[1] M. J. Hoban, E. T. Campbell, K. Loukopoulos, D. E. Browne, New J. Phys. 13 023014 (2011)

[2] M. J. Hoban, D. E. Browne, Phys. Rev. Lett. 107, 120402 (2011)

In this talk, I will discuss some new results in the model of exact quantum query complexity. In this model, we wish to compute a boolean function f with certainty using the smallest possible number of queries to the input. It is known that quantum algorithms exist in this model which can achieve significant speed-ups over classical algorithms; however, when f is a total function (ie. there is no promise on the input) the best quantum speed-up known is a factor of 2.

I will present several families of total boolean functions which have exact quantum query complexity which is a constant fraction of their classical query complexity. These results were originally inspired by numerically solving the semidefi nite programs characterising quantum query complexity for small problem sizes. I will also discuss the model of nonadaptive exact quantum query complexity, which can be characterised in terms of coding theory.

The talk will be based on the paper arXiv:1111.0475, which is joint work with Richard Jozsa and Graeme Mitchison.

We present an approach to quantum state generation problems that can be thought of as a quantum analog of the classical rejection sampling method (von Neumann, 1951). We assume that a black box is given that produces a coherent superposition of (possibly unknown) quantum states with some amplitudes. The problem is to prepare a coherent superposition of the same states, albeit with different target amplitudes. We exhibit a quantum algorithm for this problem and analyze its cost using semidefinite programming. As an application, we derive a quantum algorithm for the hidden shift problem for an arbitrary Boolean function. A bound on the runtime of this algorithm can be obtained by "water-filling" the Fourier spectrum.

Joint work with Maris Ozols and Jeremie Roland and based on arXiv:1103.2774

We advocate a new approach of addressing hidden structure problems and finding efficient quantum algorithms. We introduce and investigate the Hidden Symmetry Subgroup Problem (HSOP), which is a generalization of the well-studied Hidden Subgroup Problem (HSP). Given a group acting on a set and an oracle whose level sets define a partition of the set, the task is to recover the subgroup of symmetries of this partition inside the group. The HSOP provides a unifying framework that, besides the HSP, encompasses a wide range of algebraic oracle problems, including quadratic hidden polynomial problems. While the HSOP can have provably exponential quantum query complexity, we obtain efficient quantum algorithms for various interesting cases. To achieve this, we present a general method for reducing the HSOP to the HSP, which works efficiently in several cases related to symmetries of polynomials. The HSOP therefore connects in a rather surprising way certain hidden polynomial problems with the HSP. Using this connection, we obtain the first efficient quantum algorithm for the hidden polynomial problem for multivariate quadratic polynomials over fields of constant characteristic. We also apply the new methods to polynomial function graph problems and present an efficient quantum procedure for constant degree multivariate polynomials over any field. This result improves in several ways the currently known algorithms.