All posts by admin

Uncategorized

Scott Aaronson Distinguished Lecture at the Informatics Forum

Friday, 13 July 2012, 4:00 pm
Room G.07, School of Informatics
10 Crichton Street, Edinburgh EH8 9AB
and afterwards for a drinks and canapé reception

Quantum Computing and the Limits of the Efficiently Computable

I’ll discuss what can and can’t be feasibly computed according to physical law. I’ll argue that this is a fundamental question, not only for mathematics and computer science, but also for physics; and that the infeasibility of certain computational problems (such as NP-complete problems) could plausibly be taken as a physical principle, analogous to the Second Law or the impossibility of superluminal signalling. I’ll first explain the basics of computational complexity, including the infamous P versus NP problem and the Extended Church-Turing Thesis. Then I’ll discuss quantum computers: what they are, whether they can be scalably built, and what’s known today about their capabilities and limitations.

Lastly, I’ll touch on speculative models of computation that would go even beyond quantum computers, using (for example) closed timelike curves or nonlinearities in the Schrodinger equation. I’ll emphasize that, even if “intractable” computations occur in a particular description of a physical system, what really matters is whether those  computations have observable consequences.

Uncategorized

Scott Aaronson Talk Schedule

Venue: School of Informatics, University of Edinburgh, Room 4.33/4.31
Times: 15:00 till 16:30

New Computational Insights from Quantum Optics

Tuesday 10/7/2012

In work with Aleksandr Arkhipov, we proposed a rudimentary form of quantum computing, based on linear optics with nonadaptive measurements; and used a connection between linear optics and the permanent function to show that even this limited model could solve sampling and search problems that are intractable for classical computers under plausible complexity assumptions.  In this talk, I’ll discuss this work in a self-contained way, and mention some of its implications for quantum computing experiments. I’ll also discuss some more general results that emerged from our work. These include a new equivalence between sampling problems and search problems based on Kolmogorov complexity; a new, linear-optics-based proof of Valiant’s famous theorem that the permanent is #P-complete; and a new classical approximation algorithm for the permanent.

Papers:
The Computational Complexity of Linear Optics
The Equivalence of Sampling and Searching
A Linear-Optical Proof that the Permanent is #P-Hard

How Much Information Is In A Quantum State?

Wednesday 11/7/2012

People often talk about the quantum state of n entangled particles as if it contained an amount of information exponential in n.  In this talk, I’ll discuss three results that suggest that, in various senses relevant for computation, prediction, and learning, quantum states
actually *don’t* behave as if they contained exponential amounts of information. Specifically, I’ll discuss the limitations of “quantum advice states,”the approximate “learnability” of quantum states from random measurement results, and the simulation of arbitrary quantum state preparation tasks by the preparation of ground states of local Hamiltonians (joint work with Andrew Drucker).

Papers:
Limitations of Quantum Advice and One-Way Communication
The Learnability of Quantum States
A Full Characterization of Quantum Advice

Talk #3

Thursday 12/7/2012

Talk #3 will be determined based on audience interest.

 

Talks

Scott Aaronson Visits QUISCO

We’re delighted to announce that Prof. Aaronson will be visiting us from July 9 till July 13 and will present a series of lectures on quantum complexity theory covering topics on complexity of linear optics and information content of quantum states.

The venue is the School of Informatics, University of Edinburgh, Room 4.33/4.31 on Tuesday,  Wednesday  and Thursday July 10, 11 and 12 from 15:00 till 16:30.

We hope you can all attend this unique rejuvenating QUISCO meetings.

Biography
Scott Aaronson is an Associate Professor of Electrical Engineering and Computer Science at MIT.  He received his PhD in computer science from University of California, Berkeley and did postdocs at the Institute for Advanced Study and the University of Waterloo.  Scott’s research interests center around fundamental limits on what can efficiently be computed in the physical world.  This has entailed studying quantum computing, the most powerful model of computation we have based on known physical theory.  He also writes a popular blog, and is the creator of the Complexity Zoo, an online encyclopedia of computational complexity theory.  He is the recipient of NSF’s Alan T. Waterman Award for 2012.

I'm delighted to announce that Prof. Aaronson will be visiting us from July
9 till July 13 and will present a series of lectures on quantum complexity
theory covering topics on complexity of linear optics and information
content of quantum states.

The venue is the School of Informatics, University of Edinburgh, Room 3.44
on Tuesday,  Wednesday  and Thursday July 10, 11 and 12 from 15:00 till
16:30.

I hope you can all attend this unique rejuvenating QUISCO meetings,
Elham

BIO
Scott Aaronson is an Associate Professor of Electrical Engineering
and Computer Science at MIT.  He received his PhD in computer science
from University of California, Berkeley and did postdocs at the
Institute for Advanced Study and the University of Waterloo.  Scott's
research interests center around fundamental limits on what can efficiently
be computed in the physical world.  This has entailed studying
quantum computing, the most powerful model of computation we have based
on known physical theory.  He also writes a popular
blog<http://(www.scottaaronson.com/blog)>,
and is the creator of the Complexity Zoo <http://(www.complexityzoo.com)>,
an online encyclopedia of computational complexity theory.  He is the
recipient of NSF's Alan T. Waterman
Award<http://web.mit.edu/newsoffice/2012/aaronson-nsf-award-0308.html>for
2012.
Talks

Wednesday 30/11/2011 Talks, Edinburgh Informatics Forum

A glance of blind computing

Vedran Dunjko

13:30, IF 4.02

Abstract: In 1978, Rivest et al. have, by asking “Is computation over data which has been encrypted possible?”, opened up a proliferate area of research in cryptography. The following 30 years yielded partial results in both the classical and new domain of quantum computation: Feigenbaum et al (1989) showed that classical computation with unconditional privacy of an NP-hard function is impossible (unless PH collapses to the 3rd level) and Childs (2005) and later Aharonov et. al, reflected on this problem in the quantum domain with only partial success. Then, 2009. saw breakthroughs in both settings: Gentry offered a positive answer in terms of a classical efficient fully homomorphic encryption, and Boradbent, Fitzsimmons and Kashefi presented the Universal Blind Quantum Computation (UBQC) protocol. Gentry’s classical scheme offers computational security whereas the UBQC scheme is unconditionally secure, but the user needs modest quantum powers. In this talk we will note the highlights of the turbulent history of computation with encrypted data, address the interplay between classical and quantum results, and their impact on cryptography, interactive proof systems and the understanding of the separation between “classical” and “quantum” in information processing. Finally, we will briefly go through the details of the UBQC protocol, and provide alternative proofs of its security.

The ZX-Calculus: a graphical approach to quantum computing

Ross Duncan

4pm, IF 4.31-33

Abstract: The ZX-calculus is a graphical notation for quantum computing based on monoidal categories and the physical notion of “strong complementarity”. In this talk I’ll explain what string complementarity is, and introduce the ZX-calculus. I’ll also demonstrate some recent applications of the calculus to problems in and around quantum computing.

Meetings

Wine and Cheese Event 2/12/2011

Dear QUISCO members, QUISCO-philles and associated wonderful people,

It is our pleasure to invite you to the very first QUISCO Wine and Cheese Event, on Friday, 2nd December 2011, at University of Edinburgh’s Informatics Forum. The Event will commence at 5pm at the 4th floor miniforum. Kids, partners, friends are most welcome to join!

Mission and vision: The idea is to institutionalise this event every first Friday of the month, where quantum and non-quantum people can socialize, discuss, and enjoy great wine and cheese in a very informal friendly atmosphere:
Students: you get to bug your supervisors
Supervisors: you get to converse your students
Researchers in general: mingle, discuss, expand your interests and start new collaborations!

During the course of the first event we will also brainstorm a bit about the actual format of the Events to come, based on the heart’s desires of the attendees.

For the reasons of simplicity, for the first Event, it is a BYOB & C festivity: contribute with a bottle of wine or juice, and ofc. cheese if you can. Please do us the honor and join us to make this fun idea a success!!

For any additional information feel free to contact me at the following e-mail address and cell phone number:
email: vd51 (at) hw ac uk
cell: +44 7907 980 936

Hope to see you soon!

Kind Regards,
Vedran Dunjko

p.s. If you choose to join us at a later stage of the event, please keep my number

Admin

New Student Representative

We welcome Electra Eleftheriadou as a student representative for Strathclyde. We are on the lookout for other students representatives and we are not restricted to only one per site.

Daniel.

Admin

New QUISCO Site

We’re moving the old QUISCO website to this new version. Please bear with us till we have transferred all the material over.

Daniel Oi,
QUISCO Dogsbody.