|
2007
|
| |
January
9: IQI Seminar
Stephen
Jordan, MIT
3:00 pm, 74 Jorgensen
Title: Error
correcting codes for adiabatic quantum computation
Abstract:
Recently, there has been growing interest in using adiabatic quantum computation
as an architecture for experimentally realizable quantum computers. One of the
reasons for this is the idea that the energy gap should provide some inherent
resistance to noise. It is now known that universal quantum computation can be
achieved adiabatically using 2-local Hamiltonians. The energy gap in these Hamiltonians
scales as an inverse polynomial in the problem size. In joint work with Edward
Farhi and Peter Shor, stabilizer codes are obtained which can be used to produce
a constant energy gap against 1-local and 2-local noise. The corresponding fault-tolerant
universal Hamiltonians are 4-local and 6-local respectively, which is the optimal
result achievable within this framework.
|
January
16: IQI Seminar
Scott Aaronson,
University of Waterloo
3:00 p.m., 74 Jorgensen
Title: Quantum
copy-protection
Abstract:
In the classical world, copy-protecting
software is trivially impossible -- not that that's stopped people from trying!
But what if your program is a quantum state? Could there exist quantum states
that let us efficiently evaluate a function f, but don't let us efficiently prepare
more states with which to evaluate f? In this talk I'll (1)
give a nontrivial example of a class of programs that *can* be quantumly copy-protected,
under a computational assumption related to (but stronger than) the hardness of
the Nonabelian Hidden Subgroup Problem;
(2) give a nontrivial example of a
class of programs that *can't* be quantumly copy-protected; and
(3) show that
in the black-box setting, *all* programs can be quantumly copy-protected except
the ones that are like my second example. The
third result uses two components that might be of independent
interest: (i)
an explicit construction of "pseudorandom quantum states," and (ii)
a common generalization of the No-Cloning Theorem and the sqrt(n) lower bound
for quantum search.
|
January
23: IQI Seminar
Superpolynomial speedups using almost any quantum
circuit
Aram Harrow, University of Bristol
3:00 p.m., 74 Jorgensen
Title: Quantum
copy-protection
Abstract:
The first provable separation between
quantum and classical polynomial time (relative to an oracle) was due to Bernstein
and Vazirani in 1993. Their construction used Hadamard transforms to achieve a
separation between O(1) quantum queries and Omega(n) classical queries, then amplified
this using a recursive construction to a polynomial upper bound for quantum time
vs. a superpolynomial classical lower bound. We strengthen the recursive construction
so it can be used with bounded-error quantum circuits, and show how similar superpolynomial
separations can be obtained when the Hadamard transforms are replaced with a variety
of other circuits, including the quantum Fourier transform on the symmetric group,
and most random circuits on n qubits of length Omega(n^3). This
is joint work with Sean Hallgren.
|
February
20: IQI Seminar
Matthew Leifer,
Perimeter Institute
3:00
p.m., 74 Jorgensen
Title: Cloning
and broadcasting in generalized probabilistic theories
Abstract:
Motivated by the question of what lies behind the information processing
abilities of quantum theory, several authors have begun to investigate information
theoretic phenomena in more general probabilistic frameworks. A framework proposed
by Barrett for this purpose is essentially the finite dimensional special case
of a much older framework first proposed by Mackey in the 1950s, and later developed
by Ludwig, Foulis and Randall, Bugajski, Holevo and others. This framework supports
states from which "super-quantum"
correlations may be obtained,
which violate Bell inequalities to a larger extent than allowed by quantum theory,
without permitting signaling. In this talk, I will give generic analogs of the
no- cloning and no-broadcasting theorems that apply to all theories within this
framework, and comment on the relation of the latter to the information theoretic
derivation of quantum theory proposed by Clifton, Bub and Halvorson. This
talk is based on joint work with Howard Barnum, Jon Barrett and Alex Wilce (quant-ph/0611295).
|
February
21: Group Meeting
Robert Spalek,
UC Berkeley
5:30pm
156 Jorgensen
Title: Recent
advances in the quantum adversary method
Abstract:
The quantum
adversary method is a very versatile lower bound technique on the quantum query
complexity of a function. Since the time of a computation is at least as big as
the number of queries asked, it also lower-bounds the time complexity. The first
such bound was Omega(sqrt(n)) for quantum search, proved in 1996 by Bennett, Bernstein,
Brassard & Vazirani before the Grover search algorithm, which matches this
bound, was discovered! In
2000, the bound was generalized by Ambainis to all functions. Despite the simplicity
of his formula the bounds are tight for most interesting functions. Since 2003,
several people independently developed a weighted version of this method. It turned
out that all these variants can only give bounds that are limited by the certificate
complexity of the function. After
sketching the method, I would like to present two recent advances in this field: 1.
The first one is a joint work with Peter Hoyer and Troy Lee. (Peter will have
given a talk on this at the SQUINT workshop, so I can skip completely this topic
if the audience wants.) The
original adversary bound can be expressed using norms of certain non-negative
matrices. By allowing negative coefficients in the "adversary matrix",
we get a new quantity that is still a lower bound on the quantum query complexity,
but for a different reason than before! Furthermore, the new bound sometimes breaks
the certificate complexity. 2.
The second one is at the moment a work in progress. The
intuition behind the original adversary bound is to define a so-called "progress
function" and upper-bound the difference of the value of this function at
time t+1 and t. Now, by upper-bounding the RATIO of the value at time t+1 and
t instead of the DIFFERENCE, we get a new lower-bound method, probably incomparable
with the old one. The recent method by Ambainis can be greatly simplified using
this formalism.
|
March
6: IQI Seminar
Lara Faoro, Rutgers
3:00 p.m., 74 Jorgensen
Title: Decoherence
in Josephson qubits: noise phenomenological model and its microscopic origin
Abstract:
Despite remarkable breakthroughs of recent years, the realization
of quantum computer using small superconducting circuits containing Josephson
junctions remain far away. Neither of these circuits in fact satisfies the stringent
requirements on the amount of allowed decoherence imposed by the fault-tolerant
quantum computation.
The important source of decoherence in Josephson qubits
is a low frequency noise in charge, critical current and flux with S(f)~1/f spectrum;
but Josephson devices are also seriously affected by quantum spurious two level
systems, responsible for high frequency noise. Connection between low and high
frequency noise features have been suggested in recent experiments and different
microscopic mechanisms and effective models have been proposed to explain the
observed spectral features.
In view of recent developments in error corrections,
where it has been shown that the overhead required by the error correcting protocols
depends crucially on the rate and nature of the physical errors, it is important
to establish the complete phenomenological description of the noise in Josephson
devices. This task can only be achieved once the microscopic origin of the noise
is understood. In
this talk, I will first discuss the phenomenological model used to describe the
noise in superconducting qubits. The model is still incomplete. Special emphasis
will be given to the discussion of its missing parts and to the description of
the discrete nature of the noise, that is characterized by the interplay between
coherent quantum impurities, responsible for high frequency noise, and incoherent
impurities responsible for random telegraph noise signals and low frequency non-Markovian
and non Gaussian 1/f noise.
Then I will briefly review, the current theoretical
models for the microscopic origin of low 1/f frequency noise in charge, critical
current and flux in Josephson qubits.
|
March
13: IQI Seminar
Robert Spekkens, University
of Cambridge
3:00 p.m., 74 Jorgensen
Title: Contextuality
and nonclassicality
Abstract:
The Bell-Kochen-Specker theorem establishes the impossibility of a noncontextual
hidden variable model of quantum theory, or equivalently, that quantum theory
is contextual. I propose an (operational) generalization of the definition of
noncontextuality that extends its applicability to preparation procedures and
unsharp (nonprojective) measurements. This generalization elucidates the sense
in which nonlocality is an instance of contextuality. Furthermore, many proofs
of the impossibility of embedding quantum theory within a classical model, including
very early proofs by von Neumann and Schroedinger, are found to be proofs of contextuality
by its lights. Finally, a standard notion of nonclassicality, the appearance of
negative values in quasi-probability representations of quantum theory (such as
the Wigner representation) -- once corrected for deficiencies -- is found to be
coincident with the generalized notion of contextuality.
|
April
3: IQI Seminar
Todd Brun, USC
3:00 p.m., 74 Jorgensen
Title: Entanglement-assisted
quantum error correction
Abstract:
The problem of decoherence in quantum computation and communication has been most
cogently addressed by the use of quantum error-correcting codes, with almost all
known codes described by the stabilizer formalism. We show how this formalism
can be extended to include entanglement-assisted codes, defined by a non-commuting
``stabilizer,''
and including standard quantum error-correcting codes as
a special case. We give a construction of these codes from classical linear codes
over GF(4), with no restriction that the classical codes satisfy the dual-containing
constraint. In particular, high-performance modern codes (such as Turbo and LDPC
codes) can be used to construct high-performance quantum codes. We discuss how
entanglement-assisted codes can be used either with pre-existing entanglement
(as in entanglement-assisted channels) or as catalytic codes, without prior entanglement.
Finally we briefly describe how this formalism can be combined with the idea of
operator quantum error-correcting codes, to produce entanglement-assisted operator
codes.
|
April
24: IQI Seminar
Durdu Guney
3:00 p.m., 74 Jorgensen
Title: Toward photonic crystal quantum circuit boards and networks
Abstract:
All of the approaches for quantum information processing have their own advantages,
but unfortunately also, their own drawbacks. Ideally, one would merge the most
attractive features of those different approaches in a single alternative technology.
We envision that the large-scale photonic crystal integrated circuits and fibers
could be the basis for robust and compact quantum circuit boards and processors
of the next generation quantum computers and networks. Cavity QED, solid state,
and (non)linear approaches for computing and optical fiber approach for communications
are the most promising candidates to be improved through this novel technology.
In my talk I will try to give some preliminary prospects for the above vision.
To achieve that I will first talk about the creation of entanglement and implementation
of quantum logic gate operations using a three-dimensional photonic crystal single-mode
cavity. Then I will go from gate-level to circuit-level and describe an integrated
conditional teleportation and readout circuit based on a photonic crystal single
chip.
|
May
1: IQI Seminar
Jim Harrington,
LANL
3:00 p.m., 74 Jorgensen
Title: Practical
error correction for quantum key distribution
Abstract:
Quantum key distribution (QKD) provides a means for securely sharing secret bits
among distant parties by using a quantum channel with sufficiently low noise and
a public authenticated classical channel for communications. One of the important
steps in a QKD protocol is to identify and correct the errors from the quantum
transmission. To date, most QKD experiments have utilized some version of Cascade
for error correction, which requires many rounds of communication back and forth.
In most realistic settings, available bandwidth and desired speed of a QKD system
may require forward error correction instead, but it appears to be an open research
problem of identifying good error-correcting codes for the practical case.I
plan to give an overview of this research problem, giving attention especially
to the error sources in QKD systems, as well as presenting some preliminary results
of using low-density parity-check codes.
|
May
8: IQI Seminar
Paolo Zanardi, USC
3:00 p.m., 74 Jorgensen
Title: Geometry of quantum criticality
Abstract:
Berry phases and the quantum-information theoretic notion of fidelity have been
recently used to analyze quantum phase transitions from a geometrical perspective.
In this talk we describe how to unify these two approaches showing that the underlying
mechanism is the critical singular behaviour of a complex tensor over the Hamiltonian
parameter space.
This is achieved by performing a scaling analysis of this
quantum geometric tensor in the vicinity of the critical points. This analysis
allows one to understand all previous results on general grounds.
|
May
15: IQI Seminar
Nick Bonesteel, Florida
State University
3:00 p.m., 74 Jorgensen
Title: Finding
braids for topological quantum computation
Abstract:
In a topological quantum computer, quantum information is stored in exotic states
of matter which are intrinsically protected against decoherence, and quantum computation
is carried out by adiabatically dragging quasiparticle excitations around one
another so that their world-lines form “braids” in 2+1 dimensional space
time. In this talk I will describe efficient 2+methods for finding explicit braiding
patterns which can be used to carry out arbitrary quantum algorithms in a topological
quantum computer using so-called “SU(2) level k” particles --- particles
which correspond (up to Abelian phases) to the quasiparticle excitations in the
Read-Rezayi sequence of fractional quantum Hall states. Time permitting, I will
also discuss recent work on random chains of interacting SU(2) level k particles.
|
May
22: IQI Seminar
Pawel Wocjan, University
of Central Florida
3:00 p.m., 74 Jorgensen
Title: Quantum
algorithms for identifying hidden polynomial functions graphs
Abstract:
We introduce
the Hidden Polynomial Function Graph Problem as a natural generalization of an
abelian Hidden Subgroup Problem where the subgroups and their cosets correspond
to graphs of linear functions over a finite field F_q. For the Hidden Polynomial
Function Graph Problem the functions are not restricted to be linear but can also
be multivariate polynomial functions of higher degree. For
a fixed number of indeterminates and bounded total degree the Hidden Polynomial
Function Graph Problem is hard on a classical computer as its black box query
complexity is polynomial in q. In contrast, this problem can be reduced to a quantum
state identification problem so that the resulting quantum query complexity does
not depend on q. For univariate polynomials we construct a von Neumann measurement
for distinguishing these states. We relate the success probability and the implementation
of this measurement to certain classical problems involving polynomial equations.
We present an efficient algorithm for hidden univariate polynomial functions by
establishing that the success probability of the measurement is lower bounded
by a constant and that it can be implemented efficiently for fixed degree. These
results are obtained with the help of tools from algebraic geometry allowing us
to make specific statements about properties of generic morphisms between affine
spaces.
|
July
10: IQI Seminar
Nicolas Cerf, University
of Brussels
3:00 p.m., 74 Jorgensen
Title: Gaussian
protocols for quantum key distribution
Abstract:
I will review the continuous-variable quantum key distribution protocols that
are based on the Gaussian modulation of Gaussian states, in particular coherent
states. I will analyze the unconditional cryptographic security of these protocols
by using an entanglement-based description supplemented with a physical model
of measurement.
In this context, I will stress the fundamental role played
by Gaussian attacks. Finally, I will consider a larger family of Gaussian protocols
that can be made more robust with respect to excess noise in the channel.
|
August
7: IQI Seminar
Falk Unger, CWI
3:00 p.m., 74 Jorgensen
Title: Perfect
parallel repetition theorem for quantum XOR proof systems
Abstract:
We consider a class of two-prover interactive proof systems where each prover
returns a single bit to the verifier and the verifier's verdict is a function
of the XOR of the two bits received. Such proof systems, called XOR proof systems,
have previously been shown to characterize MIP (= NEXP) in the case of classical
provers but to reside in EXP in the case of quantum provers (who are allowed to
share a priori entanglement).
We show that, when the provers are allowed to
coordinate their behavior with a shared entangled quantum state, a perfect parallel
repetition theorem holds in the following sense.
The prover's optimal success
probability for simultaneously playing a collection of XOR proof systems is exactly
the product of the individual optimal success probabilities.
This property
is remarkable in view of the fact that, in the classical case (where the prover's
can only utilize classical information), it does not hold.
The
theorem is proved by analyzing parities of XOR proof systems using semidefinite
programming techniques, which we then relate to parallel repetitions of XOR games
via Fourier analysis.
|
October
10: IQI Seminar
Rahul Jain, University
of Waterloo
4:00 p.m., 74 Jorgensen
Title: Direct
product theorems for communication complexity via sub-distribution bounds with
application to communication-entanglement trade-offs in quantum communication
protocols
Abstract:
A basic question in complexity theory is whether the computational
resources required for solving k independent instances of the same problem scale
as k times the resources required for one instance. We investigate this question
in various models of classical communication complexity.We
define a new measure, the subdistribution bound, which is a generalization of
the well-studied rectangle or corruption bound in communication complexity. We
prove that the one-way version of this bound tightly captures the one-way public-coin
randomized communication complexity of any relation. More importantly, we show
that the bound satisfies the strong direct product property under
product
distributions, for both one- and two-way communication. This way we recover and
generalize, in a unified manner, several recent results on the direct product
question, including those due to Klauck et al. [04], Beame et al. [07], Gavinsky
[06], and de Wolf [06]. As
an application to one of our direct product results we present a communication-entanglement
trade-off in quantum communication protocols. This is a strengthening of a recent
result due to Gavinsky [06].
|
October
16: IQI Seminar
Peter Love, Haverford
College
3:00 p.m., 74 Jorgensen
Title: Simple
universal Hamiltonians
Abstract:
It
has been established that local lattice spin Hamiltonians can be used for universal
adiabatic quantum computation. While the simplest quantum spin model, the 2-local
Ising model with 1-local transverse field, was shown not to be universal, it can
be rendered universal and QMA-complete by adding a tunable 2-local transverse
XX or ZX coupling. Universal adiabatic quantum computation could therefore be
realized with only two distinct types of interaction. In addition, one would like
to restrict the range of distinct coupling strengths in the Hamiltonian, and I
will describe some constructions which do so.
|
October
26: IQI Seminar
Steven van Enk,
University of Oregon
4:00 p.m., 114 E. Bridge
Title: Rotating
photons
Abstract:
We
propose a quantum theory of rotating light beams and study some of its properties.
Such beams are polychromatic and have either a slowly rotating polarization or
a slowly rotating transverse mode pattern. We show there are, for both cases,
three different natural types of modes that qualify as rotating, one of which
is a new type not previously considered. We discuss differences between these
three types of rotating modes on the one hand and non-rotating modes as viewed
from a rotating frame of reference on the other. We present various examples illustrating
the possible use of rotating photons, mostly for quantum information processing
purposes. We introduce in this context a rotating version of the two-photon singlet
state.http://arxiv.org/abs/0707.3434
|
November
6: IQI Seminar
Sandy Irani, UCI
3:00 p.m., 74 Jorgensen
Title: The
power of quantum systems on a line
Abstract:
In
this talk, we discuss the computational strength of finite dimensional quantum
particles arranged on a line. We prove that adiabatic computation is equivalent
to standard quantum computation even when the adiabatic quantum system is restricted
to 2-local interactions of nearest neighbors on a line. The particles in this
construction require 9 states per particle. We then adapt this construction to
show that the 2-local Hamiltonian for 12 state particles on a line is QMA-complete.
QMA is the quantum analog of NP. This result contrasts with the classical analog
in which one-dimensional Max-2-SAT with nearest neighbor constraints is in known
to be in P.
Similar results were obtained independently by Aharonov, Gottesman
and Kempe. The work appears jointly in FOCS 2007.
|
November
13: IQI Seminar
Alioscia
Hamma, USC
3:00 p.m., 74 Jorgensen
Title: The
quantum phase transition to topological order and topological entropy
Abstract:
Topological
order is a type of quantum order that cannot be described by symmetry (or the
breaking of it) and local order parameters. Topologically ordered states have
degenerate ground states depending on the topology, gapped excitations and are
very resistant against perturbations. These exotic phases of matter have therefore
attracted attention to be suitable for robust quantum computation: topological
quantum computing.
But what describes them? So in other terms, what is the
order parameter for them? Entanglement is an answer. Entanglement contains features
that can tell apart a topological phase from a normally ordered phase. It can
spot the quantum phase transitions between them and serve as (nonlocal) order
parameter. Are there other more refined features that can classify topological
orders? In this talk we will present analytical and numerical results about the
quantum phase transition from the spin polarized state to the ground state of
the Kitaev's toric code model. We will show that the qpt is detected by quantities
like energy density, entanglement, and the novel ground state fidelity. Then we
will show that Topological Entropy not only spots the transition, but also serves
as order parameter.
We will also show results for a perturbed model with random
perturbations.
|
November
20: IQI Seminar
Eduardo Novais,
Duke University
3:00 p.m., 74 Jorgensen
Title: Resilient
quantum computation in correlated environments
Abstract:
In
this seminar, I discuss a quantum computer in a correlated environment protected
from decoherence by QEC. Using a method inspired by the perturbative renormalization
group, I rephrase the condition for resilient quantum computation as a dimensional
criterion for
relevance or irrelevance of operators. Finally, I will make
a parallel with the theory of quantum phase transitions.
|
December
4: IQI Special Seminar
Matthew Hastings, LANL
3:00 p.m., 74 Jorgensen
Title: An overview of quantum expanders
Abstract:
Expander graphs play a large role in computer science and information theory, with applications such as derandomizing algorithms and constructing error correcting codes. Recently, a quantum version of these expanders has been developed. I will give an overview of the classical case, and then discuss one application of the quantum case to constructing states of quantum spin chains with the seemingly contradictory properties of large entanglement entropy and small correlations. I will then give a probabilistic construction of quantum expanders, and close with various speculative applications to quantum many-body systems.
|
December
7: IQI Special Seminar
Pavel Lougovski, University of Oregon
1:30 p.m., 214 Steele
Title:Verifying multimode entanglement
Abstract:
We discuss how to construct a method for N-partite entanglement detection. In contrast to conventional objects of research -- mainly systems of few gaussian modes -- we rather concentrate on the mode entanglement for non-gaussian states. We adopt and modify conventional entanglement measures such as entanglement witnesses and uncertainty-based entanglement criteria to the case of non-gaussian N-mode states. We show how to verify genuine N-mode entanglement -- in particular when the total photon number is small -- with just a few measurements.
|
December
14: IQI Special Seminar
Raymond Laflamme, IQC, University of Waterloo
4:00 p.m., 74 Jorgensen
Title: NMR
and quantum information processing
Abstract:
I will give a brief overview of recent experimental results
using NMR technology and focus in particular on two of them: algorithmic cooling
and an efficient characterization of noise.
Algorithmic cooling is a method
to efficiently remove entropy from a system. I will describe how this can be done
thinking about it as a computation and show experimental results demonstrating
multiple rounds of heat-bath algorithmic cooling in a nuclear magnetic resonance
quantum information processor. I will also describe a second set of experiments
that uses a general symmetrisation method that allows for direct experimental
characterisation of relevant features of the noise. This framework was applied
to develop an efficient experimental protocol for estimating multi-body correlations
in the noise. I will show result from an experiment implementing these ideas.
|
