COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > CQIF Seminar > Quantum matchgate computations and linear threshold gates

## Quantum matchgate computations and linear threshold gatesAdd 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. |
## Other listsNeuroscience Seminars History of Medicine Seminars Simple Ideas that Change the World## Other talksTowards a whole brain model of perceptual learning Deep & Heavy: Using machine learning for boosted resonance tagging and beyond Type I IFN induces CXCL13-driven B cell recruitment to the lung to enable tertiary GC formation Viral evolution on sub-phylogenetic timescales The MMHT view of the proton Annual General Meeting Computing knot Floer homology TBC Atiyah Floer conjecture Fumarate hydratase and renal cancer: oncometabolites and beyond Existence of Lefschetz fibrations on Stein/Weinstein domains CANCELLED Ñande reko: alterity and (non-)participatory research with guaraní women in Bolivia |