| Andris Ambainis |
Quantum Lovasz local lemma (slides) |
|
The Lovasz Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of "weakly dependent" criteria. We show that the LLL extends to the quantum setting, where events are replaced with subspaces of the state space.
We then apply our Quantum LLL to quantum satisfiability (QSAT), quantum analogue of the satisfiability problem. In the k-QSAT problem, we have to verify whether there exists n-qubit pure state such that its k-qubit reduced density matrices have support on prescribed subspaces. Using quantum LLL, we show that random instances of the k-QSAT problem have solution, as long as the ratio between the number of constraints and
the number of variables is at most c 2^k/k^2, for a suitable constant c. This gives a major improvement over previously used methods, which were able to show the existence of solutions for ratios up to 1.
This is a joint work with Julia Kempe (Tel Aviv University) and Or Sattath (Hebrew University). Preprint number: arxiv:0911.1696. |
| Joseph Fitzsimons |
Universal blind quantum computation and interactive proofs (slides) |
|
In this talk I will provide a brief introduction to the notion of interactive proofs, and discuss how this relates to verification of quantum computers. In particular, I will focus on the problem of whether or not the results of a quantum computer can be classically verified. For problems contained within NP the answer is clearly that they can be verified. There do exist problems, however, inside BQP which are not believed to be contained within NP, and it is unclear how such results can be verified. I will introduce the notion of 'blind quantum computation', and how it can be exploited in the context of verification and interactive proof systems. Blind quantum computation refers to the problem of allowing Alice to have Bob carry out a quantum computation for her such that Bob learns nothing about the computation that he performs. I will introduce a protocol for performing secure blind computation and show that it allows any quantum computation to be verified by a classical verifier given to non-communicating quantum provers, or by a semi-classical verifier using only a single quantum prover. The existence of such a protocol has consequences for the study of complexity theory, as it allows quantum verifiers in multiple-prover interactive proofs to be replaced with classical verifiers. |
| Aram Harrow |
A quantum algorithm for solving linear systems of equations (slides) |
|
Solving linear systems of equations is a common problem that arises
both on its own and as a subroutine in more complex problems: given a
matrix A and a vector b, find a vector x such that Ax=b. We consider
the case where one doesn't need to know the solution x itself, but
rather an approximation of the expectation value of some operator
associated with x, e.g., x'Mx for some matrix M. In this case, when A
is sparse, N by N and has condition number kappa, classical algorithms
can find x and estimate x'Mx in O(N sqrt(kappa)) time. Here, we
exhibit a quantum algorithm for this task that runs in poly(log N,
kappa) time, which in some cases is an exponential improvement over
the best classical algorithm. |
| Richard Jozsa |
On the classical simulation of quantum circuits (slides) |
|
A fundamental goal of quantum computation is to understand the relationship of classical to quantum computational power and to identify specific quantum features that may be exploited for novel algorithmic benefit. A mathematically precise approach to these heuristic goals is to study the extent to which various kinds of quantum computations (perhaps involving only restricted quantum resources) can be classically simulated. We will discuss recent results in this direction, on the classical simulation properties of two classes of quantum circuits, and speculate upon their significance. (a) We will introduce the notion of a matchgate, a particular kind of 2-qubit gate. It may then be shown that circuits of matchgates, restricted to act on only nearest-neighbour qubits, are classically efficiently simulable, even though such quantum processes can for example, develop complicated entanglements. Furthermore, if the matchgates are allowed to act on just next-nearest-neighbour qubits as well, then we recover fully universal quantum computation. (b) We will discuss quantum circuits comprising only commuting gates. Despite their tantalising apparent simplicity we will outline evidence that such quantum computational processes are unlikely to be classically efficiently simulable, even in a suitable weak approximate sense.
These results were obtained in collaborations, variously with A. Miyake, B. Kraus, J. Watrous, M. Bremner and D. Shepherd. |
| Ashley Montanaro |
An efficient test for product states (slides) |
|
The detection and characterisation of entanglement is a basic task in quantum information theory. In this talk, I will discuss a test that can distinguish efficiently between pure product states of n quantum systems and states which are far from product.
A key application of the test is to quantum Merlin-Arthur games, where it can be used to simulate arbitrarily many unentangled provers by two unentangled provers, up to a constant loss of soundness. This implies that boolean satisfiability can be verified given two short unentangled quantum proofs, which in turn implies complexity-theoretic obstructions to several tasks in quantum information theory. In particular, correctness of the product state test paradoxically implies a hardness result for testing entanglement of mixed states.
This talk is based on the paper arXiv:1001.0017, which is joint work with Aram Harrow.
|
