I’m interested in most areas of quantum information science. I think the best description of my research interests was given by Ashley Montanaro (one of my office mates) who said, “Mick is a physicist who is computer science curious.”.
My most recent work has been focused on two distinct areas: 1. Instantaneous quantum computation, and 2. Resources for measurement-based quantum computation. If you are interested I’ve written a couple of short summaries of these lines of research below.
Instantaneous Quantum Computation
Recently I co-authored a paper with Dan Shepherd titled Instantaneous Quantum Computation which is a somewhat grandiose name for a particular computational paradigm that can be constructed from quantum circuits whose “Hamiltonians” have all commuting terms. If each term that appears in the Hamiltonian is interpreted as being a gate then the time ordering of the gates in the circuit is irrelevant to the output. If you view such computations in terms of measurement-based models they can be generated without any adaptive feed-forward, hence all the measurements can be performed instantaneously which is why we use the term.
In this paper we define a computational class which we dub IQP (Instantaneous Quantum Polytime) and we discuss at length computational problems where IQP oracles are supplied to some classical player. We define IQP via X-programs, which is a set of programs which takes a description of a Hamiltonian and outputs samples from a probability distribution that is defined by an evolution according to that Hamiltonian from some fiducial state.
Somewhat surprisingly we demonstrated that it is possible to hide a code in the description of an X-program in such a way that the hidden code induces a bias in set of output probabilities of the program which is almost certainly undetectable unless you know how the original code was hidden. What’s more we give an argument that this bias cannot be reproduced by some classical simulation of the IQP machine.
What is this good for? There are a number of architectures for IQP capable devices which are, in principle if not in practice, simpler to build than a quantum computer. Our analysis essentially details an algorithm which can be performed on such devices which cannot be simulated classically. As such it can be used as a test for the successful engineering of a non-trivial quantum computation device which is somewhat easier than other tests (for instance the successful implementation of Shor’s algorithm).
Where is this work going? There are any number of questions stemming from the original IQP paper that remained unanswered. To begin with, most of our arguments about the complexity of the algorithm we develop are based on heuristic analysis and not formal proofs. As is well known, if we were to prove a separation between, say, BPP and IQP then we would also separate P from PSPACE which would be a significantly more important result!
That said, there is a lot of scope for strengthening some of the arguments in the paper especially regarding the difficulty of revealing a code hidden in an X-program (according to our algorithm) and the best classical simulation of an X-program. There are also a lot of variations on definitions and ways of strengthening or weakening the capability of the IQP paradigm which lead to interesting observations.
This paper should soon appear in Proceedings of the Royal Society A under the title Temporally Unstructured Quantum Computation which is probably a more appropriate title given that for most architectures “Instantaneous” isn’t a particularly appropriate term.
Resources for measurement-based quantum computation
Measurement-based quantum computation is, to me, a particularly interesting version of quantum computation. The fact that all unitary operations can be driven almost exclusively via adaptive measurements on some easily described pure state is a remarkable feature of quantum mechanics. I am interested in generalizations of this computational model.
In cluster state quantum computation the initial state of the computer is a particularly simple multi-qubit entangled state. Essentially, the state is generated by a rectangular lattice of commuting two-qubit interactions. The width of this lattice is determined by size of the problem to be solved and the depth is determined by the depth of the corresponding quantum circuit for the problem.
Because of some special features of the cluster state it is very easy to describe the effect of single-qubit projective measurements on the state. Indeed it is so simple that it is possible to see how particular a measurement outcome on a given qubit can be interpreted as applying a unitary operations on its neighbouring qubits. This, in essence, allows one to determine a simple set of update rules for the state of the computer which have a one-to-one correspondence with gates in the quantum circuit model.
These very special features are not unique to the cluster state but it is very hard to identify sets of states, measurements, and update rules that admit a computational model that is equivalent to the standard model of quantum computation. One of the major difficulties encountered when playing with this problem is finding update rules that are actually simple. Given that we think that quantum computers are hard to simulate classically, it isn’t that surprising that this task is very difficult.
Recently I co-authored a paper with Andreas Winter and Caterina Mora in which we examined whether or not it is possible for random pure states to be used as a resource for quantum computation. The answer was a resounding “no”.
We set up the result by interpreting some abstract measurement-based quantum computer as being a polynomially restricted classical computer which runs an algoithm by controlling and interpreting single-qubit (or few-qubit) measurements on a pure quantum state. Then, by using arguments from the theory of measure concentration, we show that if the quantum state is random then with overwhelming probability the output of the computation can be simulated by a BPP capable device.
Now, random pure states are a somewhat elaborate class of resources. To begin with a randomly chosen pure state cannot be simulated in exponential time on a quantum computer. In essence our result is talking about a set of states that have a natural mathematical definition but may not exist naturally. But the importance of this result is that it definitively rules out any way of exploiting the large amount of entanglement present in such states for the purposes of computation.
The main theorem in our paper is focused on computations that solve decision problems, we also show that this line of thinking can be naturally extended to sampling problems – loosely speaking we demonstrated that a polynomially bounded classical control computer when assisted by a random pure state is not much good at sampling the output of a normal quantum computer.
Finally, we extended our results to pure states which are randomly chosen from sets of states with bounded Schmidt rank. The importance of this final extension was to demonstrate that there are states which cannot be used as a resource for measurement based models that have more entanglement that cluster states yet do not have the same entangling properties as random states.
Are random pure states useful for quantum computation? Has been submitted to Physical Review Letters.