Quantum matchgate computations and linear threshold gates

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

• Maarten van den Nest
• Thursday 31 March 2011, 14:15-15:15
• MR14, Centre for Mathematical Sciences.

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

The theory of matchgates is of interest in various areas in physics and computer science. Matchgates occur in e.g. the study of fermions and spin chains, in the theory of holographic algorithms and in several recent works in quantum computation. In this talk I will discuss a paper in which we completely characterize the class of boolean functions computable by unitary two-qubit matchgate circuits with some probability of success. We show that this class precisely coincides with that of the linear threshold gates. The latter is a fundamental family which appears in several fields, such as the study of neural networks. Using the above characterization, we further show that the power of matchgate circuits is surprisingly trivial in those cases where the computation is to succeed with high probability. In particular, the only functions that are matchgate-computable with success probability greater than 3/4 are functions depending on only a single bit of the input.

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
• MR14, Centre for Mathematical Sciences
• bld31

Note that ex-directory lists are not shown.