We're meeting tomorrow at the usual time (11:00) and place (6-310).
Also, forwarded from a message from Madhu Sudan, Umesh Vazirani will be
giving two talks at Harvard, today at 4pm and tomorrow at 1:00.
-----------
Thursday:
Umesh is giving a talk at the Harvard CS Colloquium *today (4-5pm in
MD G115)* on "Testing Quantum Devices and Quantum Mechanics". (Talk is
disjoint from the material tomorrow.)
Reading Group this Friday with Umesh Vazirani
Our speaker this Friday will be Umesh Vazirani who'll walk us through a
1-dimensional quantum system and show us how to compute its ground state in
polynomial time. For the deterministic/probabablistic analog of this
problem, a simple dynamic program would solve the 1-d problem, but for
quantum systems many technical barriers need to be overcome; and Umesh will
explain the math behind this!
As usual talk will be from 1:15-4:15, pizza at 1, break around 2:30. Talk is
in 20 Garden Street (in Cambridge obviously!): After you enter the building
take the stairwell one floor down to the ground level and use your nose to
find the pizza!
Madhu
--------------------
Abstracts:
Testing Quantum Devices and Quantum Mechanics
21 Sep
Computer Science Colloquium Series
Umesh Vazirani - University of California Berkeley
Thursday, September 21, 2017 -
4:00pm to 5:15pm
Maxwell Dworkin G115
The tremendous recent progress in the physical realization of devices
based on the principles of quantum mechanics also throws up a fundamental
challenge: how to test quantum devices, which are by nature imperfect and
susceptible to uncontrollable faults. The classical verifier of such a
device is necessarily at a disadvantage due to the exponential power of
quantum systems, as well as the severe limit on the accessible information
about the state of the system via a measurement.
Nevertheless, an exciting sequence of results show that uniquely quantum
features such as entanglement (Einstein's "spooky action at a distance")
together with the key computer science concept of interactive proofs, can
be leveraged to make such testing possible. I will describe how such
testing can thwart a malicious adversary in quantum cryptographic settings
such as quantum key distribution and certifying quantum random numbers.
More sophisticated such schemes can be used to verify that a quantum
computer is truly quantum. At a conceptual level, such tests of quantum
devices are really tests of quantum mechanics that go well beyond the
famous Bell tests, that disproved Einstein's objections to quantum
mechanics.
I will also describe a more pragmatic but principled approach to the
testing of large scale quantum annealers - by performing a quantum Turing
test comparing the quantum annealer to a suitable classical benchmark. I
will discuss the results of applying such a test to the D-Wave 108 qubit
quantum annealer, as well as the ~1000 qubit D-Wave 2X quantum annealer.
The talk will be aimed at a broad audience of computer scientists and
physicists, and I will not assume a background in quantum computing.
https://www.seas.harvard.edu/calendar/event/104011
-----------------
Friday, September 22, 2017 at 20 Garden Street: Speaker: Umesh Vazirani
(Berkeley) Topic: Rigorous RG algorithms for simulating 1D quantum systems.
Computing low energy states of quantum many body systems is a central
challenge in condensed matter physics. From a computational complexity
viewpoint these are near optimal solutions to (quantum) constraint
satisfaction problems. Mathematically, the problem is specified by a
succinctly described Hamiltonian - an exponentially large matrix, and the
challenge is to find the eigenstates with small eigenvalues. A priori it is
not even clear whether such eigenstates can be succinctly described, let
alone computed efficiently. In this talk I will describe novel combinatorial
arguments showing that low energy states for systems of particles with
nearest neighbor interactions in 1D can be described succinctly, leading to
an efficient classical algorithm for computing them. The algorithm provides
a new perspective on the well known Renormalization Group (RG) formalism
within condensed matter physics.
Over the last quarter century the famous Density Matrix Renormalization
Group (DMRG) algorithm has been widely used as a numerical heuristic for
identifying ground and low energy states of 1D quantum systems. A recent
implementation of our algorithm shows promise for outperforming DMRG in hard
cases with high ground space degeneracy or near criticality.
The talk will be aimed at a broad audience of computer scientists and
physicists, and I will not assume a background in quantum computing.
Based on joint work with Itai Arad, Zeph Landau and Thomas Vidick.
http://theory.csail.mit.edu/reading-group
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip