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:30 Simon Perdrix Libby Heaney Robin Kothari 11:30
12:00 Yasuhiro Takahashi Matthew McKague Bill Rosgen 12:00
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

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
... (local food info) (local food info) ...

Invited Speakers:
Accepted Talks:

Abstracts of invited talks:

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 speed-up 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 qubus-type quantum devices and discuss system designs and architecture for scalable large-scale 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 higher-dimensional 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.

Abstracts of accepted talks:

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 S2 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:quant-ph/ 0912.5537]. Our proof is based on optimal one-shot Quantum State Merging and the Post-Selection Technique for quantum channels.

Dan Browne, Elham Kashefi and Simon Perdrix:
Computational depth complexity of measurement-based quantum computation

In this paper, we mainly prove that the "depth of computations" in the one-way model is equivalent, up to a classical side-processing of logarithmic depth, to the quantum circuit model augmented with unbounded fan-out gates. It demonstrates that the one-way 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 one-way model and the quantum circuit model. Since one-way model has the same parallel power as unbounded quantum fan-out circuits, the quantum Fourier transform can be approximated in constant depth in the one-way model, and thus the factorisation can be done by a polytime probabilistic classical algorithm which has access to a constant-depth one-way quantum computer. The extra power of the one-way model, comparing with the quantum circuit model, comes from its classical-quantum 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 (d2(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 (d4(log*N ) ||H||)1+o(1) . To achieve this, we decompose a general sparse Hamiltonian into a small sum of Hamiltonians whose graphs of non-zero 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 measure-and-prepare 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 cb-norm bounds on the asymptotic convergence of quantum cloning to state estimation, and bounds on the quantum capacity of the k-particle 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 spin-chains

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 many-body 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 transmission-chain.

Libby Heaney:
Teleportation with mode entanglement of a single massive particle [pdf]

Mode entanglement exists naturally between regions of space in ultra-cold 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 sensibly-reduced non-zero polynomial agreeing with the problem, even on just its zero-inputs, 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 multi-qubit entanglement in terms of Rényi and Tsallis entropies

We consider the full spectrum of one-parameter generalizations for von Neumann entropy, namely quantum Rényi-α entropy and Tsallis-q entropy, and prove monogamy of entanglement in multi-qubit systems. Using Rényi-α entropy, we provide a class of monogamy inequalities of multi-qubit entanglement for α ≥ 2, and another class of monogamy inequalities in terms of Tsallis-q entropy for 2 ≤ q ≤ 3.

Matthew McKague and Michele Mosca:
Generalized self-testing and the security of the 6-state protocol

We define a family of simulations of quantum experiments with two interesting properties. First, we are able to define a self-test which may be passed only by simulations within the family. This extends work of Mayers and Yao and Magniez et al. in self-testing of quantum apparatus. Second, all the simulations in the family may be used to implement a secure 6-state 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 speed-ups 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 non-isometry is QMA-complete [pdf]

Determining the worst-case 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 LU-LC conjecture. An important consequence of our result is that surface codes do not have any encoded non-Clifford 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 {ZX, (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 one-qubit 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.

 Posters (more details in Abstract Booklet):

[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 Lamas-Linares and Christian Kurtsiefer:
Narrowband PPKTP source for entangled photons [abstract]

Muhammad Mubashir Khan, Jie Xu and Almut Beige:
Quantum Key Distribution with High Eavesdropping Error-rate 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:
Measurement-based and Adiabatic Computation: A Hybrid Programmable Scheme

A. Windhager, M. Suda, C. Pacher, M. Peev and A. Poppe:
Quantum Interference between a Single-Photon 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 Perez-Delgado and Pieter Kok:
Black-box parameter estimation with continuous variables - Optimality of Heisenberg limit

 Rump Session:

This year at TQC we will host a "rump" session of short talks 2pm-3: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 2-10 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 (2-3 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 e-mail submissions to phytqc@googlemail.com (note: different e-mail 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 e-mailed.

Revision: 14th April 2010