Recent results on the classical simulation of quantum circuits

Add to your list(s) Download to your calendar using vCal

• Richard Jozsa (CQC)
• Thursday 20 May 2010, 14:15-15:15
• MR3, Centre for Mathematical Sciences.

If you have a question about this talk, please contact Jonathan.

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

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR3, Centre for Mathematical Sciences
• bld31

Note that ex-directory lists are not shown.