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 > Isaac Newton Institute Seminar Series > Boson-Sampling in the light of sample complexity

## Boson-Sampling in the light of sample complexityAdd to your list(s) Download to your calendar using vCal - Eisert, J (Freie Universitt Berlin)
- Friday 06 September 2013, 14:00-14:30
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Mathematical Challenges in Quantum Information Boson-Sampling is a classically computationally hard problem that can – in principle – be efficiently solved with linear quantum optical networks. Very recently, a rush of experimental activity has ignited with the aim of developing such devices as feasible instances of quantum simulators. Even approximate Boson-Sampling is believed to be hard with high probability if the unitary describing the optical network is drawn from the Haar measure. In this work we show that in this setup, with probability exponentially close to one in the number of bosons, no symmetric algorithm can distinguish the Boson-Sampling distribution from the uniform one from fewer than exponentially many samples. This means that the two distributions are operationally indistinguishable without detailed a priori knowledge. We carefully discuss the prospects of efficiently using knowledge about the implemented unitary for devising non-symmetric algorithms that could potentially improve upon this. We conclude that due to the very fact that Boson-Sampling is believed to be hard, efficient classical certification of Boson-Sampling devices seems to be out of reach. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsComputing and Mathematics Type the title of a new list here Ver Heyden de Lancey Medico-Legal Lectures## Other talksPlanck Stars: theory and observations Ethics for the working mathematician, seminar 10: Mathematicians being leaders. Identifying new gene regulating networks in immune cells CPGJ Academic Seminar: "The teaching professions in the context of globalisation: A systematic literature review" Drugs and Alcohol The race to solve the solar metallicity problem with neutrinos and discover dark matter |