TQC 2010
Location: School of Music

(PDF of programme)
Time  Tuesday 13th  Wednesday 14th  Thursday 15th  Time 
8:30  Registration & coffee  coffee  coffee  8:30 
9:00  Opening remarks  9:00  
9:30  Frank Verstraete  Kae Nemoto  Anton Zeilinger  9:30 
10:00  10:00  
10:30  Ashley Montanaro  Mario Berta  Benjamin Johnson  10:30 
11:00  BREAK  BREAK  BREAK  11:00 
11:30  Simon Perdrix  Libby Heaney  Robin Kothari  11:30 
12:00  Yasuhiro Takahashi  Matthew McKague  Bill Rosgen  12:00 
12:30  LUNCH  LUNCH  LUNCH  12:30 
13:00  13:00  
13:30  13:30  
14:00  Frédéric Magniez 
rump session
14:00  15:30 
Ronald de Wolf  14:00 
14:30  14:30  
15:00  Pradeep Sarvepalli  Carlo Di Franco  15:00  
15:30  BREAK 
poster session
(with refreshments) 15:30  18:00 [pdf]  BREAK  15:30 
16:00  Jeong San Kim  Giulio Chiribella  16:00  
16:30  Martin Aulbach  Arleta Szkola  16:30  
17:00  Closing remarks  17:00  
17:30  17:30  
...  ...  
19:30 
Conference Dinner 19:30  22:00 
19:30  
...  (local food info)  (local food info)  ... 
Frédéric
Magniez (LRI, Paris):
Application of Phase Estimation in Quantum Walks
The hitting time of a classical random walk (Markov chain) is the
time required to detect the presence of  or equivalently, to find 
a marked state. The hitting time of a quantum walk is subtler to
define; in particular, it is unknown whether the detection and
finding problems have the same time complexity. Remarkably the use
of phase estimation was useful to clarify, to unify and to simplify
previous attempts. We will start by defining a very general notion
of quantum walks, and by investigating the notion of quantum hitting
time. We will present a quantum algorithm for the problem of
detecting a marked element, whose complexity is related to the
quantum hitting time. Further, we will prove a tight quadratic
speedup for the quantum hitting time of the quantum analogue of any
reversible ergodic Markov chain. We will conclude by presenting a
generic method for designing quantum walk based algorithms via their
classical analogues. We will illustrate the method through important
applications of quantum walks in quantum algorithms.
Kae Nemoto (NII, Tokyo):
Architecture and system design for quantum computer and quantum networks
Qubus computation is a type of quantum information processing (QIP)
where computational qubits couple through a quantum bus (qubus).
Such computation is flexible in terms of physical systems,
properties and it scales exceptionally well. In this talk we
introduce a number of new designs for qubustype quantum devices and
discuss system designs and architecture for scalable largescale
quantum computer and quantum networks.
Frank Verstraete
(University of Vienna):
Quantum Metropolis Sampling
We present a new quantum algorithm for simulating thermal states of
strongly correlated quantum systems by generalizing the Metropolis
algorithm to the quantum setting. This validates the quantum
computer as a universal simulator. We discuss the efficiency of the
algorithm, and elaborate on the conditions for quantum detailed
balance. [arXiv:0911.3635]
Ronald de Wolf (CWI, Amsterdam):
Quantum proofs for classical theorems
Quantum computing provides us with new algorithms and communication
protocols, but the techniques developed in this field can also be
used as tools for analyzing and proving results
about classical algorithms and mathematical
constructions. This is analogous to the use of complex numbers to
prove statements about real functions, or the use of the
probabilistic method. This talk will survey some recent examples of
this phenomenon, in the areas of coding theory and polynomial
approximations. It will cover a subset of the recent survey paper
by Andrew Drucker and myself, which is available at
http://arxiv.org/abs/0910.3376
Anton Zeilinger
(University of Vienna):
Fundamental Experiments from Single Neutrons via Bell Tests to
Exploring Higher Dimensional Hilbert Space
Fundamental experiments in Quantum mechanics initially concerned
tests of predictions like the 1 phase factor of a spinor wave
function under full rotation or precision tests of the linearity of
the Schrödinger equation using cold neutrons. These, and also
the first tests of Bell's inequality were motivated by purely
fundamental interest. Completely unexpected such fundamental
investigations became crucial for the development of the field of
quantum information science. In the talk the status of such
experiments will be reviewed and the prospects for a loophole free
test of Bell's inequality will be discussed. Another interesting
development concerns new experiments in higherdimensional Hilbert
spaces. Orbital angular momentum states of photons provide one
possibility for such experiments. Conceptionally most interesting
are entanglement experiments where the notion of entangled
singularities is still a fascinating topic to be explored
further. Another interesting approach to higher dimensional Hilbert
spaces is to use multiport devices which permit to investigate mode
entanglements of photons created in the process of parametric down
conversion. I suggest that the fundamental physics in higher
dimensional Hilbert spaces is largely unexplored terrain. One
fascinating question is that of mutually unbiased bases (MUBs) in a
Hilbert space of dimension N. It is proposed that using the
techniques just mentioned one can actually study these bases and
their transformations experimentally. This talk is also intended to
provide encouragement to investigate the formal structures of
systems in Hilbert spaces of higher dimensions.
Martin Aulbach, Damian Markham and
Mio Murao:
The maximally entangled symmetric state in terms of the
geometric measure
[pdf]
The maximally entangled state in terms of the geometric measure of
entanglement is investigated for pure states of multipartite
systems. Here we focus on the subset of symmetric states, and ask
which state of a n qubit symmetric system is the maximally
entangled one. By using the Majorana representation we analyze
the entanglement of n qubit symmetric states in a visually
accessible way by n points on the Bloch sphere. For
symmetric states of three to twelve qubits we present the
putatively maximally entangled states, and for the case of
positive coefficients the maximally entangled states are derived
by analytical and numerical methods for up to twelve qubits. We
compare our optimization problem on the Bloch sphere with two
classical optimization problems on the S^{2} sphere,
namely Tóth's problem and Thomson's problem.
Mario Berta, Matthias Christandl and
Renato Renner:
A Conceptually Simple Proof of the Quantum Reverse Shannon
Theorem
[pdf]
The Quantum Reverse Shannon Theorem states that any quantum channel
can be simulated by an unlimited amount of shared entanglement and
an amount of classical communication equal to the channel's
entanglement assisted classical capacity. In this paper, we provide
a new and conceptually simple proof of this theorem, which has
previously been proved in [Bennett et al., arXiv.org:quantph/
0912.5537]. Our proof is based on optimal oneshot Quantum State
Merging and the PostSelection Technique for quantum channels.
Dan Browne, Elham Kashefi and Simon
Perdrix:
Computational depth complexity of measurementbased quantum
computation
In this paper, we mainly prove that the "depth of
computations" in the oneway model is equivalent, up to a
classical sideprocessing of logarithmic depth, to the quantum
circuit model augmented with unbounded fanout gates. It
demonstrates that the oneway model is not only one of the most
promising models of physical realisation, but also a very powerful
model of quantum computation. It confirms and completes previous
results which have pointed out, for some specific problems, a depth
separation between the oneway model and the quantum circuit model.
Since oneway model has the same parallel power as unbounded quantum
fanout circuits, the quantum Fourier transform can be approximated
in constant depth in the oneway model, and thus the factorisation
can be done by a polytime probabilistic classical algorithm which
has access to a constantdepth oneway quantum computer. The extra
power of the oneway model, comparing with the quantum circuit
model, comes from its classicalquantum hybrid nature. We show that
this extra power is reduced to the capability to perform unbounded
classical parity gates in constant depth.
Andrew Childs and Robin
Kothari:
Simulating sparse Hamiltonians with star decompositions
[pdf]
We present an efficient algorithm for simulating the time evolution
due to a sparse Hamiltonian. In terms of the maximum degree d
and dimension N of the space on which the
Hamiltonian H acts, this algorithm uses
(d^{2}(d + log^{*}N ) H)^{1+o(1)}
queries. This improves the complexity of the sparse Hamiltonian
simulation algorithm of Berry, Ahokas, Cleve, and Sanders, which
scales like
(d^{4}(log^{*}N ) H)^{1+o(1)}
. To achieve this, we decompose a general sparse Hamiltonian into a
small sum of Hamiltonians whose graphs of nonzero entries are
disjoint unions of star graphs and efficiently simulate each of
these pieces.
Giulio Chiribella:
Optimal pure state estimation as a randomized universal
cloning
[pdf]
We consider the optimal measureandprepare channel from M to k
copies of an unknown pure state and show that for k < M the
channel is equal to a random loss of M−s particles followed by
universal cloning from s to k copies. This result can be used to
derive an alternative proof of the standard finite quantum de
Finetti theorem, to derive cbnorm bounds on the asymptotic
convergence of quantum cloning to state estimation, and bounds on
the quantum capacity of the kparticle restriction of any channel
with permutationally invariant output.
Carlo Di Franco, Mauro
Paternostro and Myungshik Kim:
Bypassing state initialisation in perfect state transfer
protocols on spinchains
Although a complete picture of the full evolution of complex quantum
systems would certainly be the most desirable goal, for particular
Quantum Information Processing schemes such an analysis is not
necessary. When quantum correlations between only specific elements
of a manybody system are required for the performance of a
protocol, a more distinguished and specialised investigation is
helpful. Here, we provide a striking example with the achievement of
perfect state transfer in a spin chain without state initialisation,
whose realisation has been shown to be possible in virtue of the
correlations set between the first and last spin of the
transmissionchain.
Libby Heaney:
Teleportation with mode entanglement of a single massive
particle
[pdf]
Mode entanglement exists naturally between regions of space in
ultracold atomic gases. It has, however, been debated whether this
type of entanglement is useful for quantum protocols. This is due
to a particle number superselection rule that restricts the
operations that can be performed on the modes. In this paper, we
show how to exploit the mode entanglement of just a single particle
for the teleportation of an unknown quantum state of a spatial mode.
We detail how to create any initial quantum state and how to perform
Bell state analysis on two of the modes. We show that two of the
four Bell states can always be reliably distinguished, while the
other two may need to be grouped together depending on whether a
phase locking criterion can be satisfied.
Benjamin Johnson:
The Polynomial Degree of Recursive Fourier Sampling
We present matching upper and lower bounds for the "weak"
polynomial degree of the recursive Fourier sampling problem from
quantum complexity theory. The degree bound is h+1, where h is the
order of recursion in the problem’s definition, and this bound is
exponentially lower than the bound implied by the existence of a BQP
algorithm for the problem. For the upper bound we exhibit a degree
h+1 real polynomial that represents the problem on its entire
domain. For the lower bound, we show that any sensiblyreduced
nonzero polynomial agreeing with the problem, even on just its
zeroinputs, must have degree at least h+1. The lower bound applies
to representing polynomials over any Field.
Jeong San Kim and Barry C
Sanders:
Monogamy of multiqubit entanglement in terms of Rényi and
Tsallis entropies
We consider the full spectrum of oneparameter generalizations for
von Neumann entropy, namely quantum Rényiα entropy and
Tsallisq entropy, and prove monogamy of entanglement in multiqubit
systems. Using Rényiα entropy, we provide a class of
monogamy inequalities of multiqubit entanglement for α ≥
2, and another class of monogamy inequalities in terms of Tsallisq
entropy for 2 ≤ q ≤ 3.
Matthew McKague and Michele
Mosca:
Generalized selftesting and the security of the 6state
protocol
We define a family of simulations of quantum experiments with two
interesting properties. First, we are able to define a selftest
which may be passed only by simulations within the family. This
extends work of Mayers and Yao and Magniez et al. in selftesting of
quantum apparatus. Second, all the simulations in the family may be
used to implement a secure 6state QKD protocol.
Ashley Montanaro:
Quantum search with advice
[pdf]
We consider the problem of search of an unstructured list for a
marked element x, when one is given advice as to where x might be
located, in the form of a probability distribution. The goal is to
minimise the expected number of queries to the list made to find x,
with respect to this distribution. We present a quantum algorithm
which solves this problem using an optimal number of queries, up to
a constant factor. For some distributions on the input, such as
certain power law distributions, the algorithm can achieve
exponential speedups over the best possible classical algorithm. We
also give an efficient quantum algorithm for a variant of this task
where the distribution is not known in advance, but must be queried
at an additional cost. The algorithms are based on the use of
Grover's quantum search algorithm and amplitude amplification as
subroutines.
Bill Rosgen:
Testing nonisometry is QMAcomplete
[pdf]
Determining the worstcase uncertainty added by a quantum circuit is
shown to be computationally intractable. This is the problem of
detecting when a quantum channel implemented as a circuit is close
to a linear isometry, and it is shown to be complete for the
complexity class QMA of verifiable quantum computation. This is
done by relating the problem of detecting when a channel is close to
an isometry to the problem of determining how mixed the output of
the channel can be when the input is a pure state.
Pradeep Sarvepalli and Robert
Raussendorf:
Local Equivalence of Surface Code States
[pdf]
Surface code states are an important class of stabilizer states that
play a prominent role in quantum information processing. In this
paper we show that these states do not contain any counterexamples
to the recently disproved LULC conjecture. An important consequence
of our result is that surface codes do not have any encoded
nonClifford transversal gates. We prove some interesting structural
properties of the CSS surface code states. We show that these states
can be characterized as a class of minor closed binary
matroids. This characterization could be of independent interest in
that it makes a connection with the theory of binary matroids.
Arleta Szkola and Michael
Nussbaum:
Asymptotically optimal discrimination between pure quantum
states
We consider the decision problem between a finite number of states
of a finite quantum system, when an arbitrary large number of copies
of the system is available for measurements. We provide an upper
bound on the asymptotic exponential decay of the averaged
probability of rejecting the true state. It represents a generalized
quantum Chernoff distance of a finite set of states. As our main
result we prove that the bound is sharp in the case of pure states.
Yasuhiro Takahashi:
Simple Sets of Measurements for Universal Quantum
Computation and Graph State Preparation
[pdf]
We consider the problem of minimizing resources required for
universal quantum computation using only projective measurements. We
show that the set of observables {Z⊗X,
(cosθ)X + (sinθ)Y all
θ ∈ [0, 2π)} with one ancillary qubit
is universal for quantum computation. The set is simpler than a
previous one in the sense that onequbit projective measurements
described by the observables in the set are ones only in the
(X,Y) plane of the Bloch sphere. The proof of the
universality immediately implies a simple set of observables that is
approximately universal for quantum computation. Moreover, the proof
implies a simple set of observables for preparing graph states
efficiently.
[list of posters as pdf]
(if you are missing from the list, please contact the registration desk)
Gerardo Adesso, Steve Campbell,
Fabrizio Illuminati and Mauro Paternostro:
Extremal Entanglement Transfer
Janet Anders, Stefanie Hilt, Eric
Lutz and Saroosh Shabbir:
Landauer's principle in the quantum domain
Katherine Brown, Clare Horsman, Viv
Kendon, and Bill Munro:
Cluster State generation using the qubus quantum computer
S. Chaturvedi, S. V. Vikram,
N. Mukunda, and R. Simon:
An algebraic description of quantum nets
Timothy Davidson, Simon Gay and
Rajagopal Nagarajan:
Equivalence Relations for Communicating Quantum Processes
Guiseppe Gennaro, Steve Campbell,
Mauro Paternostro and Massimo Palma:
Structural change in multipartite entanglement sharing: a random matrix approach
David Herrera Marti, Austin Fowler, David
Jennings and Terry Rudolph:
A Photonic Implementation of the Topological Cluster State Computer
Siddarth Koduru Joshi, Felix Anger, Anita LamasLinares and Christian Kurtsiefer:
Narrowband PPKTP source for entangled photons
[abstract]
Muhammad Mubashir Khan, Jie Xu and Almut Beige:
Quantum Key Distribution with High Eavesdropping Errorrate
using Two Dimensional Photon States
Soojoon Lee, Jeong San Kim, and Barry C. Sanders:
Distribution and Dynamics of Entanglement
Neil B. Lovett, Sally Cooper,
Matthew Everitt, Matthew Trevers and Viv Kendon:
Universal quantum computation using the discrete time quantum
walk
Z. Kadar, A. Marzuoli and M. Rasetti:
Topological phases, 3D state sums and boundary lattice models
Andreas Schreiber, Katiuscia
Cassemiro, Václav Potoček, Aurél Gábris,
Peter Mosley, Erika Andersson, Igor Jex and Christine
Silberhorn:
Photons Walking the Line: A Quantum Walk with Adjustable
Coin Operations
Afsoon Ebrahimi and Sina Salek:
Measurementbased and Adiabatic Computation: A Hybrid
Programmable Scheme
A. Windhager, M. Suda, C. Pacher, M. Peev and A. Poppe:
Quantum Interference between a SinglePhoton Fock State and a Coherent State
[abstract]
James Wootton, Ville Lahtinen and
Jiannis Pachos:
Experimentally Accessible Topological Memories from Simple
Stabilizer Codes
Shengjun Wu:
Nonclassical correlation and information causality
[abstract]
Marcin Zwierz, Carlos PerezDelgado
and Pieter Kok:
Blackbox parameter estimation with continuous variables 
Optimality of Heisenberg limit
This year at TQC we will host a "rump" session of short talks
2pm3:30pm on Wednesday afternoon, before the poster session. This
will give you the chance to present your work in an informal
environment and we encourage submissions from students, and new as
well as experienced researchers. As an added incentive, all speakers
will receive chocolate, with bonus bars for those who keep within
their allotted time! The session will include:
1) Short
talks of length 210 mins on current research or open problems. These
talks should aim to give an overview of the work, without significant
amounts of technical detail.
2) Announcements (23
minutes) of upcoming events or jobs.
3) 1 minute summaries
of the posters on display, which can be accompanied by a single slide.
This will give you the opportunity to advertise your poster before the
session. We highly encourage everyone who is participating in the
poster session to do this: anyone who is presenting a poster will be
automatically accepted for this part of the rump session.
We will be accepting submissions from now until 6pm on Tuesday, and
will publish the programme by 9am on Wednesday. Please email
submissions to phytqcgooglemail.com (note: different email
address) with an abstract (title only for poster talks), length of
talk (up to 10 mins) and any necessary slides (pdf format please).
If you have any questions, either email or come and talk to
one of us at the conference. It will also be possible to hand in
abstracts to any of the conference organisers. However the slides
will later need to be emailed.
Revision: 14th April 2010