Quantum Computation & Information Group seminars are listed below. Our seminars are announced by email; if you would like to be added to the mailing list, please contact Stefan Baeuml. Other seminars of related groups which may be of interest include
The Theoretical
Physics seminar series in the Physics Department
There are no upcoming seminars.
Previous seminars:
**28 May 2014 16:00**(NSQI Discussion room)- David Lyons
- tba
**26 March 2014 16:00**(NSQI Discussion room)- Will Matthews
- tba
**05 March 2014 16:00**(NSQI Discussion room)- Maris Ozols
- The classical analogue of quantum mechanics
**05 March 2014 14:00**(NSQI Discussion room)- Anyone
- Joint experiment and theory discussion
**29 January 2014 16:00**(NSQI Discussion room)- Marcin Markiewicz
- Genuinely multi-point temporal quantum correlations and universal one-way quantum computing on 1D cluster states
**16 January 2014 12:30**(NSQI Discussion room)- Belen Sainz
- Probabilistic models on Contextuality scenarios and the Local Orthogonality principle
**15 January 2014 16:00**(NSQI Discussion room)- Michael Fryers
- The state collapse theorem and generalisations.
**18 December 2013 16:00**(NSQI Discussion room)- Michael Bremner
- Towards a proof of the classical intractability of quantum simulation
**11 December 2013 16:00**(NSQI Discussion room)- Naresh Sharma
- A gambling interpretation of some quantum information-theoretic quantities
**04 December 2013 16:00**(NSQI Discussion room)- Milan Mosonyi
- Renyi divergences in quantum information theory
**20 November 2013 16:00**(NSQI Discussion room)- Tamas Vertesi
- Witnessing nonlocality from separable marginals
**13 November 2013 16:00**(NSQI Discussion room)- Michael Walter
- Lower Bounds for Quantum Parameter Estimation
**16 October 2013 16:00**(NSQI Discussion room)- Anyone
- QI Experiment & theory bull session
**09 October 2013 16:00**(NSQI Discussion room)- Mateus Santos
- Quantum computers cannot control unknown operations
**02 October 2013 15:00**(NSQI Seminar room)- Bill Wootters
- What is the origin of complex probability amplitudes?
**25 September 2013 16:00**(NSQI Discussion room)- anyone
- QI Experiment & theory bull session
**18 September 2013 16:00**(NSQI Discussion room)- Min-Hsiu Hsieh
- When do Local Operations and Classical Communication Suffice for Two-Qubit State Discrimination?
**12 June 2013 16:00**(NSQI Discussion room)- Stefan Weigert
- Triples of Pairwise Canonical Observables
**05 June 2013 16:00**(NSQI discussion room)- Toby Cubitt
- Undecidability of the spectral gap problem
**30 May 2013 16:00**(NSQI Discussion room)- Lev Vaidman
- Asking photons where have they been?
**29 May 2013 16:00**(NSQI discussion room)- Niel de Beaudrap
- The Counting complexity of 2-Quantum-SAT (or: the ground-state degeneracy of frustration-free spin-1/2 Hamiltonians)
**22 May 2013 16:00**(NSQI discussion room)- Earl Campbell
- Magic-State Distillation in All Prime Dimensions Using Quantum Reed-Muller Codes
**08 May 2013 16:00**(NSQI Discussion room)- Alessandro Ferraro
- Non-classicality criteria from phase-space representations and information-theoretical constraints are maximally inequivalent
**01 May 2013 16:00**(NSQI Discussion room)- Lluis Masanes
- The existence of an information unit as a postulate of quantum theory
**25 April 2013 10:30**(Engineers House, The Promenade)- Various
- Quantum algorithms day
**10 April 2013 16:00**(NSQI Discusion room)- Jarrod McClean
- A Variational Algorithm on a Quantum Processor for Quantum Chemistry
**20 March 2013 16:00**(NSQI discussion room)- Ashley Montanaro
- Three quantum learning algorithms
**13 March 2013 16:15**(NSQI discussion room)- Simon Devitt
- From Quantum to Crowd-Sourcing; Programming a quantum computer
**13 March 2013 15:30**(NSQI discussion room)- Mohan Sarovar
- Designing light harvesting from the ground up
**20 February 2013 16:00**(NSQI discussion room)- Karoline Wiesner
- Sharpening Occam's Razor with Quantum Mechanics
**13 February 2013 16:00**(NSQI discussion room)- Tony Short
- Simulating non-locality using negative probabilities
**06 February 2013 16:00**(NSQI Discussion room)- Yeong-Cherng Liang
- From device-independent entanglement certification to quantification
**30 January 2013 16:00**(NSQI discussion room)- Jamie Vicary
- Topological Structure of Quantum Algorithms
**20 June 2012 16:00**(NSQI QI discussion room)- Matthias Kleinmann (Siegen)
- How the bipartite correlations of quantum mechanics emerge
- Host: Marcus Huber
**19 June 2012 13:30**(NSQI Seminar room)- Paul Raymond-Robichaud
- EPR, Bell's Theorem and Popescu-Rohlich boxes
**13 June 2012 16:00**(NSQI QI discussion room)- Burak Sahinoglu (ETH Zurich)
- Spectra of Tripartite Quantum States and 6j-Symbols of the Symmetric Group
- Host: Andreas Winter
**30 May 2012 16:00**(NSQI QI discussion room)- Omar Fawzi (McGill)
- Quantum to classical randomness extractors
- Host: Andreas Winter
**23 May 2012 16:00**(NSQI QI discussion room)- Joonwoo Bae (CQT)
- Quantum Steering, No-Signaling, and Optimal Quantum State Discrimination
- Host: Andreas Winter
**16 May 2012 16:00**(NSQI discussion room)- Tomoyuki Morimae (Imperial College London)
- Blind quantum computation
- Host: Akimasa Miyake
**10 May 2012 14:01**(NSQI QI discussion room)- Julio I. de Vicente (Innsbruck)
- Complete set of operational measures for the characterization of 3-qubit entanglement
- Host: Marcus Huber
**09 May 2012 16:00**(NSQI QI discussion room)- Marco Piani (IQC Waterloo)
- Relating the general quantumness of correlations and entanglement
- Host: Andreas Winter
**02 May 2012 16:00**(NSQI QI discussion room)- David Bruschi and Nicolai Friis
- TBA
**03 April 2012 16:00**(NSQI seminar room)- Renato Renner (ETH Zurich)
- The thermodynamic meaning of negative (conditional) entropy
**21 March 2012 16:00**(NSQI QI discussion room)- Janet Anders (UCL)
- Landauer's erasure principle in the strongly coupled quantum regime
- Host: Andreas Winter
**14 March 2012 16:00**(NSQI QI discussion room)- Antonio Acin (ICFO)
- Local orthogonality: a multi-partite principle for quantum correlations
- Host: Nicolas Brunner
**07 March 2012 16:00**(NSQI QI discussion room)- Peter Turner (University of Tokyo)
- The curious non-existence of Gaussian 2-designs
- Host: Jeremy O'Brien
**22 February 2012 16:00**(NSQI seminar room)- Matthew Pusey
- TBA
- Host: Nicolas Brunner
**15 February 2012 16:00**(NSQI QI discussion room)- Yu Watanabe (Tokyo University)
- Eigenstate Randomization Hypothesis: a thermalization mechanism on isolated quantum systems
- Host: Andreas Winter
**08 February 2012 16:00**(NSQI QI discussion room)- Andreas Winter
- The non-additivity saga continues: entanglement of purification
- -
**25 January 2012 16:00**(NSQI seminar room)- Alberto Montina
- Quantum dynamics as a non-Markov classical process
**07 December 2011 16:00**(NSQI QI discussion room)- Leon Loveridge
- Quantum Measurements, Conservation Laws and the Role of a Classical Limit
- Host: Steve Brierley
**30 November 2011 16:05**(NSQI QI discussion room)- Arleta Szkola
- Maximum likelihood type detectors for multiple quantum states
- Host: Andreas
**09 November 2011 16:00**(NSQI QI discussion room)- Fabrizio Illuminati
- Distance measures of entanglement and quantum correlations, and their application to the study of collective quantum systems
- Karoline Wiesner/Andreas Winter
**19 October 2011 16:00**(NSQI QI discussion room)- Josh Cadney
- Infinitely many constrained inequalities for the von Neumann entropy
**07 October 2011 12:00**(NSQI QI discussion room)- Ed Blakey (Oxford)
- Counting the Cost of Quantum Computation and Cryptography
**05 October 2011 16:00**(NSQI seminar room)- Milan Mosonyi
- Renyi relative entropies in quantum information theory
**14 September 2011 16:00**(NSQI seminar room)- Marcus Cramer
- TBA
**01 June 2011 16:00**(NSQI QI seminar room)- Matty Hoban
- Computation with Correlations and Processing with Post-selection
- Host: Nicolas Brunner
**25 May 2011 16:00**(NSQI quantum information seminar room)- Ivan Todorov (Queens University Belfast)
- Operator system structures and entanglement
**17 May 2011 14:00**(NSQI quantum information seminar room)- Toby Cubitt
- Frustratingly undecidable (or undecidably frustrating)
**06 May 2011 14:00**(NSQI QI seminar room)- Mary Beth Ruskai
- Quantum Marginals and N-representability: Some Old and New Results.
- Noah Linden
**05 May 2011 15:00**(NSQI quantum information seminar room)- Lluis Masanes
- Entanglement is unusual
- Host: Andreas Winter
**13 April 2011 15:00**(NSQI quantum information seminar room)- Miguel Navascues
- Sequential strong measurements and heat vision
- Host: Nicolas Brunner
**06 April 2011 16:00**(NSQI quantum information seminar room)- Gerardo Adesso
- All non-classical correlations can be activated into distillable
- Host: Nicolas Brunner
**05 April 2011 16:00**(NSQI quantum information seminar room)- Alex Monras (Universitat Autonoma de Barcelona)
- Characterizing and quantifying frustration in quantum many-body systems
**30 March 2011 16:00**(NSQI quantum information seminar room)- Ciara Morgan (CQT, Singapore)
- The invalidity of a strong capacity for a quantum channel with memory
**23 March 2011 16:00**(NSQI quantum information seminar room)- Ashley Montanaro (DAMTP, Cambridge)
- An exponential separation between quantum and classical one-way communication complexity
- Host: Andreas Winter
**16 March 2011 16:00**(NSQI quantum information seminar room)- Tamas Vertesi
- Nonlocality activation in the bipartite scenario
- Host: Nicolas Brunner
**09 March 2011 16:00**(NSQI quantum information seminar room)- Jan Florjanczyk (McGill)
- The locking-decoding frontier for generic dynamics
**03 March 2011 17:30**(Frank Lecture Theatre, Department of Physics)- Andreas Winter
- Quantum contextuality: inequalities and tests
- CHAOS undergraduate lecture (Bristol Physics Society) - http://www.bristolchaos.co.uk/
**23 February 2011 16:00**(NSQI quantum information seminar room)- Marcus Huber
- Exploring Multipartite Entanglement
- Host: Andreas Winter
**16 February 2011 16:00**(NSQI quantum information seminar room)- Andreas Winter
- (Non-)Contextuality of Physical Theories as an Axiom
**02 February 2011 16:00**(NSQI quantum information seminar room)- Steve Brierley
- Mutually Unbiased Bases - an overview
**26 January 2011 13:45**(NSQI quantum information seminar room)- Sevag Gharibian
- Approximation algorithms for QMA-complete problems
**15 December 2010 16:00**(NSQI quantum information seminar room)- Marcin Pawlowski
- Monogamy of nonlocality
**27 October 2010 16:00**(NSQI Quantum information theory discussion room)- Lukasz Pankowski
- Low-dimensional quite noisy bound entanglement with cryptographic key
- Host: Sandu Popescu
**30 September 2010 16:00**(NSQI quantum information seminar room)- Cedric Beny
- Classical limit from monitoring of a quantum field
- Host: Andreas Winter
**23 June 2010 13:00**(NSQI Quantum information theory discussion room)- Christian Gogolin
- Pure state quantum statistical mechanics
- Host: Andreas Winter
**16 June 2010 16:00**(NSQI Quantum information theory discussion room)- David Kribs
- Some aspects of operator theory relevant to quantum information
**25 May 2010 13:00**(NSQI Quantum information theory discussion room)- Nathaniel Johnston
- Schmidt Norms for Quantum States
- Host: Andreas Winter
**21 April 2010 16:00**(NSQI quantum information discussion room)- Robin Kothari
- Efficiently simulation of Hamiltonians
- Host: Aram Harrow
**14 April 2010 16:00**(NSQI QI discussion room)- Mafalda Almeida
- Guess your neighbour's input: a game that reveals the weakness of quantum resources
- Host: Andreas Winter
**31 March 2010 16:00**(NSQI quantum information discussion room)- Shmuel Marcovitch
- Can we derive quantum formalism from first principles?
**18 March 2010 16:00**(NSQI quantum information discussion room)- Simone Severini
- Patterns of zeros in matrices
- Host: Richard Jozsa
**10 March 2010 16:00**(NSQI quantum information seminar room)- Nilanjana Datta
- Relative entropies and entanglement monotones
- Host: Toby Cubitt
**03 March 2010 16:00**(NSQI quantum information seminar room)- Koji Azuma
- Optimal entanglement generation in hybrid quantum repeaters
- Host: Richard Jozsa
**24 February 2010 16:00**(NSQI quantum information seminar room)- Terry Rudolph
- Entanglement and the thermodynamic arrow of time
- Host: Toby Cubitt
**16 February 2010 12:00**(NSQI quantum information seminar room / TUESDAY)- David Perez-Garcia
- A quantum version of Wielandt's inequality
- Host: Toby Cubitt
**10 February 2010 16:00**(NSQI QI seminar room)- Dieter Jaksch
- Entanglement Percolation with Bipartite Mixed States
- Host: Nicolas Brunner
**27 January 2010 16:00**(NSQI quantum information seminar room)- Jiannis Pachos
- The drunken slalom
- Host: Toby Cubitt
**13 January 2010 16:00**(NSQI quantum information seminar room)- Vlad Gheorghiu
- Location of Quantum Information in Additive Graph Codes
- Host: Richard Jozsa
**17 December 2009 16:00**(NSQI quantum information seminar room)- Katherine Brown (Leeds)
- An optimally efficient technique for the generation of cluster states using a qubus quantum computer.
- Host: Clare Horsman
**16 December 2009 16:00**(NSQI quantum information seminar room)- Toby Cubitt
- Super-duper-activation of the Zero-Error Quantum Capacity
**09 December 2009 14:15**(Physics / 3.27)- Renato M. Angelo (UFPR - Brazil / Bristol)
- The paradoxical nature of quantum references frames
**03 December 2009 16:00**(NSQI quantum information seminar room / THURSDAY)- Will Matthews
- Improving zero-error classical communication with entanglement
- Host: Ashley Montanaro
**02 December 2009 16:00**(NSQI QI seminar room)- Janet Anders
- Quantum correlations and complexity
- Host: Andreas Winter
**24 November 2009 16:00**(NSQI QI seminar room / TUESDAY)- Almut Beige
- Something from nothing: Energy concentration in atom-cavity systems
- Host: Nicolas Brunner
**18 November 2009 16:00**(NSQI quantum information seminar room)- Alastair Kay
- The Entanglement Phases of Thermal Graph States
- Host: Nicolas Brunner
**05 November 2009 16:00**(NSQI quantum information seminar room)- Matthias Christandl
- The Uncertainty Principle in the Presence of Quantum Memory
- Host: Richard Jozsa
**28 October 2009 16:00**(NSQI quantum seminar room)- Jonathan Allcock
- Closed sets of non-local correlations
**07 October 2009 16:00**(NSQI seminar room)- Frederic Dupuis (Universite de Montreal)
- The decoupling approach to quantum information theory revisited
**01 October 2009 16:00**(NSQI seminar room)- Stephanie Wehner (Caltech)
- Unconditional security from noisy quantum storage
**09 September 2009 16:00**(NSQI Building seminar room)- Tim Ralph (University of Queensland)
- Can Gravitational Curvature Decorrelate Entanglement?
- The NSQI Building is on Tyndall Avenue, next to the Physics department
**09 September 2009 14:00**(NSQI seminar room)- Harry Buhrman
- A generalized Grothendieck inequality and entanglement in XOR games
- http://arxiv.org/abs/0901.2009
**17 June 2009 16:00**(3.34 Physics Department)- Yutaka Shikano (Tokyo)
- Weak Values with Decoherence
**10 June 2009 16:00**(3.21 Physics Department)- Miguel Navascues (Imperial)
- A complete criterion for separability detection
**05 June 2009 14:00**(3.21 Physics Department)- Andreas Winter
- Information causality and all that
**01 June 2009 16:00**(3.34 Physics Department)- Andrzej Dragan (University of Warsaw)
- Emergence of quantum indeterminacy from special relativity
**27 May 2009 16:00**(3.21 Physics Department)- Animesh Datta (Imperial)
- The Role of Entanglement in Quantum Computation - A Discord/ant/ story
**20 May 2009 14:15**(3.27 Physics Department)- Tobias Osborne (Royal Holloway)
- Solving frustration-free hamiltonians
- Theoretical Physics seminar series
**13 May 2009 16:00**(3.34 Physics Department)- Richard Low
- Large Deviation Bounds for k-designs
**06 May 2009 16:00**(3.21 Physics Department)- Valerio Scarani (University of Singapore)
- QKD: a million signal task
**23 April 2009 16:00**(3.21 Physics Department)- Marco Piani (IQC, Waterloo)
- Relative Entropy of Entanglement and Restricted Measurements
**22 April 2009 16:00**(3.21 Physics Department)- Fernando Brandao (Imperial)
- The complexity of poly-gapped Hamiltonians: Extending Valiant-Vazirani theorem to the probabilistic and quantum settings
**25 March 2009 16:00**(3.21 Physics Department)- Eric Chitambar (University of Michigan)
- Encoding Various Decision Problems as a Question of Entanglement Convertibility
- Note change of room
**18 March 2009 16:00**(3.34 Physics Department)- Sarah Leyton (Royal Holloway)
- A Quantum Algorithm to solve Nonlinear Differential Equations
**11 March 2009 16:00**(3.21 Physics Department)- Daniel Burgarth (Imperial)
- Indirect Hamiltonian Estimation and Restricted Control
- Note change of room.
**25 February 2009 16:00**(3.34 Physics Department)- Sandu Popescu
- Entanglement in biological systems
**18 February 2009 16:00**(3.34 Physics Department)- Joe Fitzsimons (Oxford)
- Communication and Blind Quantum Computation
**04 February 2009 16:00**(3.34 Physics Department)- Paul Skrzypczyk
- Non-locality swapping
**28 January 2009 16:00**(3.34 Physics Department)- Aram Harrow
- Quantum algorithm for solving linear systems of equations
**07 January 2009 16:00**(3.34 Physics Department)- Ivette Fuentes-Schuller (Technical University of Berlin)
- Entanglement in non-inertial frames and curved spacetime
**17 December 2008 16:00**(3.34 Physics Department)- Debbie Leung (IQC, Waterloo)
- Continuity of quantum channel capacities
**15 December 2008 16:00**(3.34 Physics Department)- Sarah Croke (Perimeter Institute)
- Approximating quantum operations using weak values
**10 December 2008 16:00**(3.34 Physics Department)- Michael Bremner
- Instantaneous Quantum Computation
**04 December 2008 16:00**(3.34 Physics Department)- Elham Kashefi (University of Edinburgh)
- Computing without Trusting
**19 November 2008 16:00**(SM3 Mathematics Department)- Ashley Montanaro
- Quantum boolean functions
**12 November 2008 16:00**(SM3 Mathematics Department)- Koenraad Audenaert (Royal Holloway)
- Quantum Tomographic Reconstruction with Error Bars: a Kalman Filter Approach
**29 October 2008 16:00**(SM3 Mathematics Department)- Gavin Brennen (Macquarie University)
- Nonlocality of Non-Abelions
**22 October 2008 16:00**(SM3 Mathematics Department)- Jonathan Matthews
- Integrated Photonics Quantum Circuits
**15 October 2008 16:00**(SM3 Mathematics Department)- Aggie Branczyk (University of Queensland)
- Quantum Computing with Kittens
**08 October 2008 14:30**(SM3 Mathematics Department)- Michel Planat (Institut FEMTO-ST, CNRS)
- Reflection groups for quantum computing
**07 October 2008 16:00**(Physics 3.34)- Simon Devitt, National Institute for Informatics, Tokyo, Japan
- Topological optical Cluster state computation with the photonic module.
**01 October 2008 16:00**(SM3 Mathematics Department)- Leandro Aolita (ICFO, Barcelona)
- Scaling laws for the decay of multiqubit entanglement
**20 August 2008 16:25**(3.34 Physics Department)- Ashley Montanaro
- Quantum algorithms for shifted subset problems
**20 August 2008 16:00**(3.34 Physics Department)- Richard Low
- Random Quantum Circuits are Approximate 2-designs
**13 August 2008 16:00**(3.34 Physics Department)- Toby Cubitt (Bristol)
- On the complexity of deciding whether a quantum channel is Markovian
**06 August 2008 16:00**(3.34 Physics Department)- Howard Wiseman (Griffith University)
- Experimentally achieving Heisenberg-limited interferometry using Quantum Information, Measurement, and Control Theory
**02 July 2008 16:00**(3.34 Physics Department)- Sean Barrett (Imperial College)
- Transitions in universality for measurement-based quantum computation in a quantum many-body system
**25 June 2008 16:00**(3.34 Physics Department)- John Mahoney and Karoline Wiesner
- An introduction into computational mechanics and the connection to quantum dynamical systems
**12 June 2008 16:00**(3.34 Physics Department)- Markus Müller
- Convex trace functions on quantum channels and the additivity conjecture
**11 June 2008 16:00**(3.34 Physics Department)- Maarten van den Nest (Max Planck Institute for Quantum Optics, Garching)
- Quantum algorithms for spin models and simulable gate sets for quantum computation
**04 June 2008 16:00**(3.34 Physics Department)- Carlos A. Perez-Delgado (Sheffield)
- Quantizing Models of Computation
**28 May 2008 16:00**(3.34 Physics Department)- Shashank Virmani (University of Hertfordshire)
- Upper bounds to fault tolerance thresholds for the common quantum computation architectures
**21 May 2008 16:00**(3.34 Physics Department)- Tony Sudbery (York)
- Mutually Unbiased Bases
**13 May 2008 16:00**(3.34 Physics Department)- Jon Yard (Los Alamos National Labs)
- Hyperactivity of the quantum capacity
**16 April 2008 16:00**(SM3 Mathematics Department)- Dan Browne (UCL)
- Measurement-based classical computation: Classifying the computational power of entangled states
**26 March 2008 16:00**(SM3 Mathematics Department)- Rob Spekkens (Cambridge)
- Contextuality from an information-theoretic perspective
**12 March 2008 16:30**(SM3 Mathematics Department)- Tobias Osborne (Royal Holloway)
- Information propagation through disordered systems
**05 March 2008 16:00**(SM3 Mathematics Department)- Rochus Klesse
- Quantum Error-Correction in correlated quantum noise
**22 February 2008 13:00**(1.06 Merchant Venturers Building)- Jeff Lundeen (Oxford)
- The search for the perfect photon
- Joint with photonics group
**19 February 2008 16:00**(1.06 Merchant Venturers Building)- Fernando Brandao (Imperial College)
- A reversible theory of entanglement and its relation to the second law
**13 February 2008 16:00**(SM3 Mathematics Department)- David W. Lyons (Lebanon Valley College)
- Maximum Stabilizer Dimension for Multiparty States
**06 February 2008 16:00**(SM3 Mathematics Department)- Aram Harrow (Bristol)
- Quantum expanders from any classical Cayley graph expander
**30 January 2008 14:00**(SM2 Mathematics Department)- Toby Cubitt (Bristol)
- The War on Additivity
**25 January 2008 13:00**(1.06 Merchant Venturers Building)- Chris Fuchs (Perimeter Institute)
- Charting the Shape of Hilbert Space: A Bit of Quantum Foundations at PI
**23 January 2008 16:00**(3.34 H.H. Wills Physics Laboratory)- Tim Spiller (HP Labs Bristol)
- The quantum-classical crossover of a field mode
- Joint with Theoretical Physics Group Seminar
**16 January 2008 16:00**(SM3 Mathematics Department)- Jonathan Walgate (Perimeter Institute)
- Completely Entangled Random Subspaces
**12 December 2007 16:00**(SM3 Mathematics Department)- Anthony Laing
- Experimental Demonstration of Measurement ID with Photonic Qubits
**06 December 2007 16:00**(1.8 Queens Building)- Alberto Politi
- Experimental demonstration of an Integrated Optical Quantum Gate
**05 December 2007 16:00**(SM3 Mathematics Department)- Renato Renner (ETH Zurich)
- On the difficulty of extracting randomness from partially untrusted quantum devices
**28 November 2007 16:00**(SM3 Mathematics Department)- David Gross (Imperial)
- Quantum Margulis expanders
**27 November 2007 14:00**(MVB 1.06)- Jürg Wullschleger
- Composable Security in the Bounded-Quantum-Storage Model
- "Enigma Variations" information security seminar
**19 November 2007 16:00**(3.27 Physics Department)- Janet Anders
- Macroscopic entanglement, critical temperature and phase transitions
**14 November 2007 16:00**(SM3 Mathematics Department)- Stephen Bartlett (Sydney)
- Quantum-computational universality and quantum phase transitions in the ground states of spin lattices
**14 November 2007 13:00**(SM2 Mathematics Department)- Terry Rudolph (Imperial College)
- Do quantum computers exist in nature?
**13 November 2007 16:00**(3.27 Physics Department)- Geoff Pryde (Griffith)
- Entanglement-free, Heisenberg-limited phase estimation
**07 November 2007 16:00**(SM3 Mathematics Department)- Marie Ericsson (Cambridge)
- Nodal free geometric phases
**01 November 2007 16:00**(1.15 Queens Building)- Marco Barbieri (University of Queensland)
- Experimental test of Bell's original inequalilty
- Photonics Research Group Seminar Programme
**24 October 2007 16:00**(SM3 Mathematics Department)- Nadav Yoran
- Classical simulability and the components of Shor's algorithm
**17 October 2007 16:00**(SM3 Mathematics Department)- Simon Benjamin (Oxford)
- Distributed entanglement generation: a promising route toward a practical quantum computer?
**16 October 2007 16:00**(3.34 Physics Department)- Libby Heaney (Leeds)
- Entanglement in the Bose-Einstein condensate phase transition
**10 October 2007 16:00**(SM3 Mathematics Department)- Karoline Wiesner
- Intrinsic quantum computation
**03 October 2007 16:00**(SM3 Mathematics Department)- Sougato Bose (UCL)
- Quantum Communication and Entanglement Distribution Through Spin Chains and Allied Systems
**20 September 2007 16:30**(SM3 Mathematics Department)- Richard Low
- Random circuits as t-designs
**20 September 2007 16:00**(SM3 Mathematics Department)- Jonathan Allcock
- Localization in Spin Chains and Quantum Error Correction
**13 September 2007 16:00**(Vice Chancellor's room, Queen's Building)- Dr. Neil Oxtoby (University of Hertfordshire)
- Realistic Quantum Trajectories and Probing Spin Baths
**31 August 2007 16:00**(4.01 MVB)- Tim Ralph (University of Queensland)
- Single Photon Side-Bands
**31 August 2007 13:00**(4.01 MVB)- Andrew White (University of Queensland)
- Photonic quantum computing: Shor's algorithm and the road to fault-tolerance
**15 August 2007 16:00**(SM4 Mathematics Department)- Tony Chefles (HP Labs)
- Capacities and distributed implementation of standard oracle operators
**07 August 2007 16:00**(4.01 Merchant Venturers Building)- André Stefanov (University of Vienna)
- Implementation of Simple Quantum Algorithms using Optical Cluster States
**28 June 2007 11:00**(4.01 Merchant Venturers Building)- Andre Ahlbrecht (TU Braunschweig)
- Braid group representations and quantum computation
**27 June 2007 16:00**(SM3 Mathematics Department)- Nilhan Gurkan (Izmir)
- Two Qubit Entanglement in Heisenberg Magnetic Chains
**20 June 2007 16:00**(SM4)- William Matthews (Bristol)
- Chernoff bound for the asymptotic LOCC discrimination of data hiding states
**06 June 2007 16:00**(SM4 Mathematics Department)- Arleta Szkola (Leipzig)
- Quantum Chernoff Distance
**30 May 2007 16:00**(SM3 Mathematics Department)- Matthias Christandl (Cambridge)
- Comparing Non-Signalling Correlations
**22 May 2007 16:00**(SM4 Mathematics Department)- Sandu Popescu (Bristol)
- Multiple-time states and measurements
- blackboard talk
**10 May 2007 16:00**(TBA)- Vladimir Korepin (Stony Brook University)
- Quantum Algorithm for Partial Search.
**09 May 2007 16:00**(SM4 Mathematics Department)- Jens Eisert (Imperial)
- Tensor networks and novel schemes for measurement-based quantum computing
**25 April 2007 16:00**(SM3 Mathematics department)- Viv Kendon (Leeds)
- Optimal computation with noisy quantum walks
**29 March 2007 16:00**(SM4 Mathematics Department)- Peter Turner (Calgary)
- Hidden degrees of freedom and distinguishability
**21 March 2007 16:00**(SM4 Mathematics department)- Tom Toffoli (Boston University)
- 'Life' without batteries is possible, can we afford it?
**13 March 2007 13:00**(MVB 1.06)- Andrew Childs (Caltech)
- Quantum algorithms for hidden nonlinear structures
**28 February 2007 16:00**(SM3 Mathematics Department)- Ashley Montanaro
- Quantum search of partially ordered sets
Abstract:Richard Feynman is known for his quote "I think I can safely say that nobody understands quantum mechanics." In this talk I will establish a weaker result, namely "to fully understand something quantum, one has to at least know what the classical equivalent of it is." As observed by Bell in 1964, quantum mechanics is not compatible with certain classical theories. Nevertheless, classical theories, such as Spekkens toy theory, can exhibit many quantum-like features. In fact, Collins and Popescu have found a strong analogy between quantum entanglement and secret classical correlations (for example, teleportation corresponds to one-time pad in their framework). I will extend their framework by describing a classical analogue of mixed quantum states. This leads to even more striking classical analogues of quantum phenomena, such as bound entanglement and superactivation of quantum capacity. To illustrate the usefulness of this unusual classical theory, I will explain a new construction of bound entangled states with smaller dimension (3x3) and higher amount of secret key, and show that local noise can increase privacy in classical secret key distillation protocols. This talk is based on a joint work (http://arxiv.org/abs/1305.0848) with Graeme Smith and John Smolin from IBM. (hide abstract) Abstract:We introduce a constructive procedure that maps all spatial correlations of a broad class of states into temporal correlations between general quantum measurements. This allows us to present temporal phenomena analogous to genuinely multipartite nonlocal phenomena, such as Greenberger-Horne-Zeilinger correlations, which do not exist if only projective measurements on qubits are considered. The map is applied to certain lattice systems in order to replace one spatial dimension with a temporal one, without affecting measured correlations. In this way we prove that 1D cluster states are in fact universal for quantum computation when we allow generalised quantum measurements. (hide abstract) Abstract:A problem that has caught the attention of the community in the past decades is that of how to characterize, from more intuitive statements, the correlations that are observed in Nature. Moreover, the study has also extended to that of understanding the probability of obtaining certain outcomes when different (and perhaps incompatible) measurements are performed on a single system. In this talk I present a new framework to study these two problems (Nonlocality and Contextuality, respectively) in a unified manner. This approach is based on graph theory, which provides us with tools to study different sets of probabilistic models, such as the classical, quantum and no-signaling sets. I also discuss the Consistent Exclusivity and the Local Orthogonality principles, as candidates to bound the sets of quantum probabilistic models, and relate them to a hierarchy of probabilistic models which arises as semi-definite programs and converges into the quantum set. (hide abstract) Abstract:Traditionally presentations of the fundamentals of quantum mechanics contain a statement along these lines: "Measuring the observable corresponding to a self- adjoint operator X leaves the system in a state which is an eigenstate of X with eigenvalue given by the result of the measurement.â We aim to recast this "wavefunction collapse postulate" as a theorem of quantum information theory, assuming that system states are described by normal states on von Neumann algebras and the effects of physical processes are described by channels (pull-back of states through normal completely positive maps). The theorem states that any channel which results in measurement of X leaving a residual system R can be uniquely written as the composite of the hypothetical operation "measure X and collapse the state accordingly" with a channel acting on the residual system alone. This is a particular case of a general construction of a "universal extension" for any channel between von Neumann algebras. I'll describe this construction and discuss the "state collapse" theorem and other applications. (hide abstract) Abstract:The efficient simulation of quantum systems is considered to be one of the most exciting potential applications of quantum computing technologies. There is an expectation that specialized quantum simulators can be engineered as a stepping stone to the development of fully universal, fault-tolerant, quantum computers. If this expectation is to be realized we must identify physical systems and sets of observables that are both simple enough to robustly implement in a near-term quantum device, yet remain a challenge to classically simulate. In this talk I will discuss several simple quantum systems that cannot be easily simulated classically that might lead to a convincing demonstration of the classical intractability of quantum simulators. (hide abstract) Abstract:It is known that repeated gambling over the outcomes of independent and identically distributed (i.i.d.) random variables gives rise to alternate operational meaning of entropies in the classical case in terms of the doubling rates. We give a quantum extension of this approach for gambling over the measurement outcomes of tensor product states. Under certain parameters of the gambling setup, one can give operational meaning of von Neumann entropies. We discuss two variants of gambling when a helper is available and it is shown that the difference in their doubling rates is the quantum discord. Lastly, a quantum extension of Kelly's gambling setup in the classical case gives a doubling rate that is upper bounded by the Holevo information. (hide abstract) Abstract:Renyi divergences play a central role in classical information theory, as they quantify the trade-off between the relevant quantities in many coding theorems. Due to the non-commutativity of density operators in quantum theory, various inequivalent formal extensions of the Renyi divergences are available, and one may wonder which one is the "right" one. One way to decide this question is to find an operational interpretation, i.e., an operationally well-defined question to which the given divergence is the answer. We will show such an operational interpretation to a recently defined Renyi divergence, introduced by independent research groups, which has already found applications in proving strong converse theorems for various channel coding problems. We also discuss some mathematical properties of these divergences, and show how they can be used to obtain very simple coding theorems in cases where there is some uncertainty about of the source or the channel. (hide abstract) Abstract:In this talk, we picture a three-party scenario, where a state of three qubits is shared between Alice, Bob, and Charlie such that all two-party reduced states AB, AC, BC are separable. We suppose that the parties have information about only these two-party marginals but not about the global three-qubit state. We exhibit separable two-party reduced states AB, AC, BC such that any global state compatible with these marginals is nonlocal. Hence, we obtain that nonlocality of three-party states can be certified from information only about separable marginals. This talk is based on a joint work with W. Laskowski and K.F. PÃ¡l. (hide abstract) Abstract:The laws of quantum mechanics place fundamental limits on the accuracy of measurements and therefore on the estimation of unknown parameters of a quantum system. In this work, we prove lower bounds on the size of confidence regions reported by any region estimator for a given ensemble of probe states and probability of success. Our bounds are derived from a previously unnoticed connection between the size of confidence regions and the error probabilities of a corresponding binary hypothesis test. In group-covariant scenarios, we find that there is an ultimate bound for any estimation scheme which depends only on the representation-theoretic data of the probe system, and we evaluate its asymptotics in the limit of many systems, establishing a general "Heisenberg limit" for region estimation. We apply our results to several examples, in particular to phase estimation, where our bounds allow us to recover the well-known Heisenberg and shot-noise scaling. (hide abstract) Abstract:One of the essential building blocks of computer programs is the ``if'' clause, which executes a subroutine depending on the value of a control variable. Similarly, several quantum algorithms rely on the possibility of applying a quantum operation conditioned on the state of a control system. Here we show that such a control cannot be performed within a quantum circuit if the operation itself is not known in advance. Nonetheless, we show that there is a natural physical way to implement controlled quantum operations. This discrepancy is due to a limitation of the standard framework for quantum computation, which overlooks the fact that physical operations act on a higher-dimensional extension of the system used for computation. Taking such a possibility into account yields a significant simplification in the implementation of certain quantum algorithms. (hide abstract) Abstract:: I begin this presentation with an attempt to explain the origin of probability amplitudes in quantum theory, but the explanation makes sense only if those amplitudes are real. This result provides motivation for studying the real-vector-space variant of quantum theory. I show how a particular model within real-vector-space quantum theory can produce the appearance of complex probability amplitudes. In this model, a special binary subsystem of the universe, called the universal rebit or âubit,â plays the role of the complex phase factor. In a certain limit the effective theory emerging from the model mimics standard quantum theory, but if we stop short of this limit the model predicts the spontaneous decoherence of isolated systems. (hide abstract) Abstract:In this paper we consider the conditions under which a given ensemble of two-qubit states can be optimally distinguished by local operations and classical communication (LOCC). We begin by completing the \emph{perfect} distinguishability problem of two-qubit ensembles - both for separable operations and LOCC - by providing necessary and sufficient conditions for the perfect discrimination of one pure and one mixed state. Then for the well-known task of minimum error discrimination, it is shown that \textit{almost all} two-qubit ensembles consisting of three pure states cannot be optimally discriminated using LOCC. This is surprising considering that \textit{any} two pure states can be distinguished optimally by LOCC. Special attention is given to ensembles that lack entanglement, and we prove an easy sufficient condition for when a set of three product states cannot be optimally distinguished by LOCC, thus providing new examples of the phenomenon known as "non-locality without entanglement". We next consider an example of $N$ parties who each share the same state but who are ignorant of its identity. The state is drawn from the rotationally invariant "trine ensemble", and we establish a tight connection between the $N$-copy ensemble and Shor's "lifted" single-copy ensemble. For any finite $N$, we prove that optimal identification of the states cannot be achieved by LOCC; however as $N\to\infty$, LOCC can indeed discriminate the states optimally. This is the first result of its kind. Finally, we turn to the task of unambiguous discrimination and derive new lower bounds on the LOCC inconclusive probability for symmetric states. When applied to the double trine ensemble, this leads to a rather different distinguishability character than when the minimum-error probability is considered. (hide abstract) Abstract:Given a quantum particle on a line, its momentum and position are described by a pair of Hermitean operators (p, q) which satisfy the canonical commutation relation. A third observable r, contained in the Heisenberg algebra generated by p and q, is known to exist which simultaneously satisfies canonical commutation relations with both position and momentum. The observables (p, q, r) form a Heisenberg triple which is not only unique (up to unitary equivalences) but also maximal (no four equi-commutant observables exist). Being invariant under a cyclic permutation, the triple (p, q, r) endows the Heisenberg algebra with an interesting threefold, largely unexplored symmetry. I will briefly discuss a number of consequences related to the existence of a Heisenberg triple and its exponentiated cousin called a Weyl triple. For example, these triples entail a unifying theory of generic properties possessed by mutually unbiased bases for both continuous and discrete variables. Furthermore, they suggest to generalise Heisenberg's uncertainty relation to an expression which involves the product of three standard deviations. (hide abstract) Abstract:The spectral gap of a quantum many-body Hamiltonian -- the difference between the ground state energy and lowest excited state in the thermodynamic limit -- plays an important role in determining the physical properties of a many-body system. In particular, it determines the phase diagram of the system, with quantum phase transitions occurring at critical points where the spectral gap vanishes. A number of famous open problems concern whether or not particular many-body models are gapped. For example, the "Haldane conjecture" states that Heisenberg spin chains are gapped for integer spin, and gapless for half-integer spin. The seminal result by Lieb-Schultz-Mattis proves the half-integer case. But, whilst there exists strong numerical evidence, the integer case remains unproven. In 2-dimensions, it has long been conjectured that the 2D AKLT model is gapped, but a proof remains elusive. In the related setting of quantum field theories, determining if Yang-Mills theory is gapped is one of the Millennium Prize Problems, with a $1 million prize attached. I will show that the general spectral gap problem is unsolvable. Specifically, there exist translationally-invariant Hamiltonians on a 2D square lattice of finite-dimensional spins, with two-body nearest-neighbour interactions, for which the spectral gap problem is undecidable. This means that there exist gapless Hamiltonians for which the absence of a gap cannot be proven in any consistent framework of mathematics. The proof is (of course!) by reduction from the Halting Problem. But the argument is quite complex, and draws on a wide variety of techniques, ranging from quantum algorithms and quantum computing, to classical tiling problems, to recent Hamiltonian complexity results, to an even more recent construction of gapless PEPS parent Hamiltonians. I will explain the result, sketch the techniques involved in the proof, and discuss what implications this might have for physics. Based on ongoing work with David Perez-Garcia and Michael Wolf. (hide abstract) Abstract:Quantum mechanics does not provide a clear answer to the question: What was the past of a photon which went through an interferometer? Various welcher weg measurements, delayed-choice which-path experiments and weak-measurements of photons in interferometers presented the past of a photon as a trajectory or a set of trajectories. We have carried out experimental weak measurements of the paths of photons going through a nested Mach-Zehnder interferometer which show a different picture: the past of a photon is not a set of continuous trajectories. The photons tell us that they have been in the parts of the interferometer which they could not have possibly reached! Our results lead to rejection of a ``common sense'' approach to the past of a quantum particle. On the other hand, they have a simple explanation within the framework of the two-state vector formalism of quantum theory. arXiv:1304.7469 (hide abstract) Abstract:Determining properties of ground states of spin Hamiltonians (such as their energy) is difficult to do in general. In order to develop analytical techniques, we may consider the simpler special case of frustration-free Hamiltonians: ones whose ground states also minimizes each Hamiltonian interaction energy. Frustration-free Hamiltonians on spin-1/2 particles represent a natural generalization of the infamous Satisfiability problem from classical computer science, which is known as Quantum-SAT. While this problem is difficult in general, natural properties of the solution space of Quantum-SAT become easy for a broad class of instances corresponding to nearest-neighbor Hamiltonians. Specifically, in many cases, we should expect to be able to determine the dimension of the ground-state manifold is usually polynomial-time. (hide abstract) Abstract:We propose families of protocols for magic-state distillationâimportant components of fault-tolerance schemesâfor systems of odd prime dimension. Our protocols utilize quantum Reed-Muller codes with transversal non-Clifford gates. We ï¬nd that, in higher dimensions, small and effective codes can be used that have no direct analogue in qubit (two-dimensional) systems. We present several concrete protocols, including schemes for three-dimensional (qutrit) and ï¬ve-dimensional (ququint) systems. At the time of publication our ï¬ve dimensional protocol was, by many measures, the best magic-state-distillation scheme yet discovered. It excels both in terms of error threshold with respect to depolarizing noise (36.3%) and the efï¬ciency measure known as yield, where, for a large region of parameters, it outperforms all first-generation qubit protocols by many orders of magnitude. (hide abstract) Abstract:I will review two celebrated criteria for defining the non-classicality of bipartite bosonic quantum systems, the first stemming from information theoretic concepts and the second from physical constraints on the quantum phase-space. Building on those, two sets of allegedly classical states are singled out: i) the set C composed of the so called classical-classical (CC) states--separable states that are locally distinguishable and do not possess quantum discord; ii) the set P of states endowed with a positive P-representation (P-classical states)--mixture of Glauber coherent states that, e.g., fail to show negativity of their Wigner function. I will show that these two defining criteria are maximally inequivalent [1], thus suggesting that there are other quantum correlations in nature than those revealed by entanglement and quantum discord. This inequivalence is further elucidated considering different applications of P-classical and CC states. Finally, an example of a family of states that reconciles both criteria will be also presented. [1] A. Ferraro and M.G.A. Paris, Phys. Rev. Lett. 108, 260403 (2012). (hide abstract) Abstract:Does information play a significant role in the foundations of physics? Information is the abstraction that allows us to refer to the states of systems when we choose to ignore the systems themselves. This is only possible in very particular frameworks, like in classical or quantum theory, or more generally, whenever there exists an information unit such that the state of any system can be reversibly encoded in a sufficient number of such units. In this talk I will show how the abstract formalism of quantum theory can be deduced solely from the existence of a suitable information unit, together with two further natural assumptions: the continuity and reversibility of dynamics, and the possibility of characterizing the state of a composite system by local measurements. This constitutes a new set of postulates for quantum theory with a simple and direct physical meaning, like the ones of special relativity or thermodynamics, and it articulates a strong connection between physics and information. (hide abstract) Abstract:The Bristol Quantum algorithms day showcases recent research in quantum algorithms. Following on from the success of the previous two years, we are delighted to have five excellent speakers: Andrew Childs, Maarten van den Nest, Ben Reichardt, Jeremie Roland, Pawel Wocjan There is no conference fee but we ask people to register if you would like to come. We are able to offer travel support to UK PhD students who donÃÂ¢ÃÂÃÂt have funding from their home institutions. (hide abstract) Abstract:Quantum computing offers promising new solutions to problems faced in quantum chemistry. In this talk I will introduce some of the methods used in classical electronic structure and their limitations. I will then show the results of recent work done as a collaboration between the Aspuru-Guzik group at Harvard and the CQP here at Bristol to dramatically reduce the technological requirements for attacking chemical problems on a quantum computer as compared to Quantum Phase Estimation. (hide abstract) Abstract:In this talk I will discuss three optimal, and varied, quantum learning algorithms, or in other words algorithms which identify an unknown object, picked from a known set of objects. The first is an algorithm for a purely quantum task: learning stabilizer states. In this problem, we are given access to a number of copies of an unknown stabilizer state of n qubits, and would like to identify the state. I will present an efficient algorithm for this task which uses O(n) copies of the state, which is optimal and represents an exponential improvement over standard tomography. The second algorithm is a generalisation of one of the earliest algorithms in quantum computing, the Bernstein-Vazirani algorithm for learning linear functions over the finite field F_2. I will present an exact quantum algorithm which learns n-variate multilinear polynomials over arbitrary finite fields and achieves an O(n) speed-up over any possible classical algorithm. Finally, I will discuss recent work on a problem dubbed "search with wildcards". Here we wish to learn an unknown bit-string, given the ability to determine whether arbitrary subsets of the bits are equal to a provided query string. I will present a quantum algorithm for this task which is based on novel ingredients and achieves a quadratic speed-up over any possible classical algorithm. This talk is based on the papers arXiv:1210.1148 (joint work with Andris Ambainis), arXiv:1105.3310, and ongoing joint work with Scott Aaronson, David Chen, Daniel Gottesman and Vincent Liew. (hide abstract) Abstract:In recent years, the theoretical and experimental development of quantum technologies has been pronounced. In the past ten years we have not only demonstrated experimental control of few qubit quantum arrays in multiple physical systems but the development of fully error corrected models of computation have been made compatible with the physical hardware. This has led to many different architecture proposals for truly scalable quantum computing. This development has illustrated a clear pathway for quantum computation and could be realised with first generation systems within the next decade. Given this fact, the time has come to address the classical side of quantum computation, namely how will such a device be programmed and controlled.Â In this talk I will outline the basic principals of the topological model of quantum computation in the context of a diamond based hardware model.Â I will not be talking necessarily about what a quantum computer is or how it performs computational tasks in a more efficient manner than a classical machine.Â Instead I will introduce the problems related to program optimisation.Â How quantum circuits are translated into the appropriate operations on the physical hardware and what needs to be done in order to reduce the number of qubits and the total computational time for large scale algorithms such as Shor's factoring routine. During this talk I will also introduce one of our current projects, "Qubit: The Quantum Computing game". Inspired by the work of the FoldIt project (the program designed to allow the general public help in solving the protein folding problem in biology), we are attempting to translate the problem of programming a large quantum computer into a game, available on portable devices such as Android and iOS.Â We are currently in the early stages of development and I will discuss the possible future for crowd sourcing the problem of programming a quantum computer and how this will help in the further development of an automated compiler language for quantum information processing. (hide abstract) Abstract:Inspired by new insights into light-harvesting in algae, bacteria, and plants, we are designing and building new frameworks for photovoltaic technologies from the ground up that imitate biological structures, and hopefully also replicate their superior performance at converting solar energy to electrical potential energy. Successfully building such biomimetic technologies requires understanding a wide variety of physical processes operating at multiple time, energy, and length scales.In this talk I will summarize theoretical and modeling research done in collaboration with K. Birgitta Whaley and Matthew Francis at UC Berkeley aimed at designing biomimetic photovoltaic technology based on self-assembling proteins that provide a scaffold for engineering the structure of light harvesting antennas. I will present our characterization of a fundamental trade-off faced when trying to simultaneously optimize energy transfer efficiency and width of spectral absorption, and will also highlight some of the challenges faced in modeling these complex systems. (hide abstract) Abstract:Mathematical models are an essential component of quantitative science. They generate predictions about the future, based on information available in the present. In the spirit of simpler is better; should two models make identical predictions, the one that requires less input is preferred. Yet, for almost all stochastic processes, even the provably optimal classical models waste information. The amount of input information they demand exceeds the amount of predictive information they output. I will show how to systematically construct quantum models that break this classical bound, and that the system of minimal entropy that simulates such processes must necessarily feature quantum dynamics. This indicates that many observed phenomena could be significantly simpler than classically possible should quantum effects be involved. The results leave an open problem: There is an unexplained gap between this minimal entropy and the lower bound given by thermodynamics. (hide abstract) Abstract:The non-local correlations which arise in quantum theory cannot be explained by any local classical model, yet they do not allow signalling between distant parties. We will show that any non-signalling correlation (including those not achievable in quantum theory) can be simulated by classical or quantum models if either the states or measurements are allowed to involve negative probabilities. This may help in analysing general probabilistic theories, and comparing them with the quantum and classical case. (hide abstract) Abstract:Entanglement certification and quantification are important parts inmany quantum information processing tasks. In this talk, I will describe some recent progress on the possibility to certifyentanglement in a device-independent manner, i.e., directly from theobserved correlations without relying on a characterization of thesystems observed or of the measurements performed. I will alsodescribe a novel technique that allows the characterization ofcorrelations derived from quantum states having additional property,such as a positive partial transpose. This, in turn, permits thequantification of entanglement in a device-independent manner. Specifically, from the observed correlations or the amount ofviolation of a given Bell inequality, we provide a lower bound on theamount of (genuine) negativity present in the measured quantum state. These bounds provide further information about the dimension of theunderlying Hilbert space or the type of entanglement responsible forthe observed correlations. (hide abstract) Abstract:We use a topological formalism to examine the Deutsch-Jozsa and single-shot Grover algorithms. This reveals important structures hidden by the conventional quantum circuit model, and allows short and visual proofs of correctness via local topological operations. This clarity allows us to propose a new generalization of Grover's algorithm, and a better understanding of a generalized Deutsch-Jozsa algorithm already in the literature. (hide abstract) Abstract:If the ultimate theory of Nature would not be quantum mechanics, how can all the experiments be explained that confirm quantum mechanics today? In [arXiv:1205.3358] we propose a mechanism that answers this question for the observable bipartite correlations. We assume that due to experimental limitations we today might have only access to a typical low-dimensional section of the full, high-dimensional post-quantum theory. In this situation there is an universal emergent model and this model itself turns out to be (with high precision) a section of quantum mechanics. It follows that the observable bipartite correlations cannot go beyond the quantum prediction. (hide abstract) Abstract:"What is proved by impossibility proofs is lack of imagination" -John Bell "Imagination is more important than knowledge" -Albert Einstein In 1935, Einstein, Podolsky, Rosen wrote that Quantum Mechanics must be incomplete under the assumption of locality and realism. While in 1964, John Bell proved that no theory of the type considered by Einstein (Hidden variable theories) is compatible with locality and realism. Locality is the principle according to which no action performed at point A can have an effect on point B faster than at the speed of light. Realism is the principle according to which any observation merely reveals what was already in the physical world. A theory is complete whenever it is capable of accounting for all physical facts. All these deep philosophical questions will be examined in the light of a toy-model based on PR-boxes. We will see how it is possible to create an exceedingly simple world which is local, realistic and where the EPR argument does not hold and which seems even more non-local than even Quantum Mechanics. (Joint work with Gilles Brassard) (hide abstract) Abstract:Does a given set of probability distributions correspond to the eigenvalue set of the global and local density matrices of a quantum state? This problem, known as quantum marginal problem, was found to be closely related to the representation theory of the symmetric group for the simplest nontrivial case, the bipartite case, by Christandl and Mitchison, and Klyachko. In this talk, we extend this work and reveal a one-to-one correspondence between the spectra of tripartite quantum states and the asymptotic behaviour of the 6j-symbols of the symmetric group. This correspondence leads to a new proof of strong subadditivity of von Neumann entropy. This is a joint work with Matthias Christandl and Michael Walter. (hide abstract) Abstract:Even though randomness is an essential resource for many information processing tasks, it is not easily found in nature. The goal of randomness extraction is to distill (almost) perfect randomness from a weak source of randomness. When the source yields a classical string X, many extractor constructions are known. Yet, when considering a physical randomness source, X is itself ultimately the result of a measurement on an underlying quantum system. When characterizing the power of a source to supply randomness it is hence a natural question to ask, how can we extract classical randomness from a quantum system. To tackle this question we here take on the study of quantum-to-classical randomness extractors (QC-extractors). We provide constructions of QC-extractors based on measurements in a full set of mutually unbiased bases (MUBs), and certain single qubit measurements. As the first application, we show that any QC-extractor gives rise to entropic uncertainty relations with respect to quantum side information. Such relations were previously only known for two measurements. As the second application, we resolve the central open question in the noisy-storage model [Wehner et al., PRL 100, 220502 (2008)] by linking security to the quantum capacity of the adversary's storage device. This is joint work with Mario Berta and Stephanie Wehner and it is available at http://arxiv.org/abs/1111.2026. (hide abstract) Abstract:Optimal quantum state discrimination (with minimum-error) is a fundamental task having lots of applications in quantum information theory. This talk aims to deliver two messages about optimal state discrimination. In the first part, state discrimination is considered in the following framework: quantum states are prepared and given by a party at a distance using the steering effect (consuming shared entanglement), and then, discrimination of given states is constrained by the no-signaling principle between two parties (one for the preparation and the other for the discrimination). Then, I show that optimal state discrimination can be determined by the compatibility of two correlations, quantum steering (i.e. entanglement) and the non-signaling measurement outcomes, without resort to the measurement postulate. From this, the necessary and sufficient conditions for state discrimination are characterized on the level of quantum states. In the second part, based on the conditions, I provide a complete solution to optimal discrimination of arbitrarily given qubit states. It is also shown that optimal state discrimination does not depend on detailed relations among given quantum states (e.g. angles) but on the geometry of given quantum states in the state space. (hide abstract) Abstract:Blind quantum computation [1] is a new secure quantum computing protocol, which enables Alice who does not have any sufficient quantum technology to delegate her computation to Bob who has a fully-fledged quantum computer in such a way that Bob cannot learn anything about Alice's input, output, and algorithm. In this talk, after quickly reviewing [1], I will explain our recent new protocols of blind quantum computation [2], which have several advantages, such as the no-signaling security and the device-independent security. [1] Broadbent, Fitzsimons, and Kashefi, FOCS 2009. [2] Morimae and Fujii, arXiv: 1201.3966 (hide abstract) Abstract:We characterize the entanglement contained in a pure 3ÃÂ¢ÃÂÃÂqubit state via operational entanglement measures. To this end we derive a new decomposition for arbitrary 3ÃÂ¢ÃÂÃÂqubit states which is characterized by five parameters (up to local unitary operations). We show that these parameters are uniquely determined by bipartite entanglement measures. These quantities measure the entanglement required to generate the state following a particular preparation procedure and have a clear physical meaning. Moreover, we show that the classification of states obtained in this way is strongly related to the one obtained when considering general local operations and classical communication. (hide abstract) Abstract:Entanglement is considered the most characteristic trait of quantum mechanics. Nonetheless, also most separable states exhibit quantum features. In this talk I will consider two scenarios to relate the general quantumness of correlations - i.e., present also in separable states - to entanglement. The first is based on the generation of entanglement in an idealized local-measurement interaction. This approach leads to the definition of entanglement-based quantifiers for the general quantumness of correlations - one for every entanglement measure - that satisfy the quite natural quantitative relation "quantumness is larger than entanglement". The second scenario is that of entanglement distribution in the presence of pre-existing correlations. In particular, we will shed light on the role of the general quantumness of correlations in the distribution of entanglement via separable states, a surprising effect originally discussed in [T. S. Cubitt et al. Phys. Rev. Lett. 91, 037902 (2003)]. The talk is largely based on M. Piani and G. Adesso, Phys. Rev. A 85, 040301(R) (2012) [arXiv:1110.2530] and T. K. Chuan et al., arXiv:1203.1268. (hide abstract) Abstract:Landauer's principle establishes a rather direct relation between the information-theoretic notion of "uncertainty" (measured in terms of entropy) and the thermodynamic notions of heat and work. It asserts that the heat dissipated by any "erasure" process (i.e., a process that resets a system into a predetermined pure state) is always lower bounded by k T H, where k is a constant, T the temperature of the environment, and H the (initial) entropy of the system. In this talk, I will present a converse statement: erasure can (in principle) always be achieved by a process with heat dissipation at most k T H. Remarkably, the validity of this statement extends to the (fully) quantum domain, where the entropy H (conditioned on the information one has about the system to be erased) may be negative. In this case, the erasure process extracts heat from the environment and transforms it into work. (hide abstract) Abstract:Landauer's principle is one of the prime examples of the connection of information theory and thermodynamics. In recent years several publications have discussed the second law of thermodynamics in the strongly coupled quantum regime and claimed its violation. Consequently Landauer's principle would also be violated. If true, these results would have powerful consequences. Perpetuum mobiles could be built as long as the operating temperature is brought close to zero. This would also have serious consequences on thermodynamic derivations of information theoretic results, such as the Holevo bound. I will review the original discussion on the model of a quantum brownian oscillator and argue why previous treatments are erroneous. It turns out that the established correlations in quantum systems at low temperatures require a rethink of how entropy, heat and work have to be calculated. I will show that a consistent treatment resolves the paradoxical situation. References: [1] S. Hilt, J. Anders, E. Lutz, S. Shabbir, PRE (R) 83:030102 (2011); [2] J. Anders, S. Shabbir, S. Hilt, E. Lutz, Elect. Proc. Comp. Sci. 26:13 (2010) (arXiv:1006.1420v1). (hide abstract) Abstract:In the last years, an intensive effort has been devoted to identify simple information principles that are satisfied by quantum correlations and violated by supra-quantum ones. Most of these principles have been formulated in a bipartite scenario. Recently it has been pointed out that intrinsically multipartite principles are necessary to recover quantum correlations for an arbitrary number of parties. We introduce the principle of local orthogonality, which is intrinsically multipartite and states that different outcomes of the same measurement by one of the parties define orthogonal events independently of the measurements applied by the other observers. We prove that local orthogonality is equivalent to the no-signalling principle in a bipartite scenario, but becomes strictly smaller for more than two parties. We use techniques from graph theory to show how bipartite supra-quantum correlations violate the principle, despite the equivalence with the no-signalling principle in the bipartite scenario. (hide abstract) Abstract:Quantum t-designs -- ensembles of pure quantum states whose t-th moments match those of the uniform distribution of states in Hilbert space -- have found a variety of applications in quantum information science and the foundations of quantum theory. They have primarily been studied in finite dimensions, where the most famous 2-designs are mutually unbiased bases and symmetric informationally complete positive operator valued measures, which are especially useful in quantum tomography. In infinite dimensions, the success of coherent state tomography, coupled with the fact that the coherent states form a 1-design, leads to the question of the existence of continuous variable 2-designs. We show that there are compelling reasons to believe that the natural candidate -- the uniform ensemble of all Gaussian states -- should work. However, we find that it not only fails, but so do all our attempts to `patch' the problem, illustrating a surprising discrepancy between discrete and continuous variable quantum mechanics. Joint work with Robin Blume-Kohout, LANL (hide abstract) Abstract:We derive an upper bound on the difference between the long-time average and the microcanonical ensemble average of observables in isolated quantum systems. We propose numerically verify, and analytically support a new hypothesis, the eigenstate randomization hypothesis (ERH), which implies that in the energy eigenbasis the diagonal elements of observables fluctuate randomly. We show that ERH includes the eigenstate thermalization hypothesis (ETH) and makes the aforementioned bound vanishingly small. Moreover, ERH is applicable to integrable systems for which ETH breaks down. [Reference: Phys. Rev. E 84, 021130 (2011).] (hide abstract) Abstract:Quantum Shannon theory aims to understand the information processing capabilities of quantum systems in the form of capacities. Unlike in Shannon's classical theory, we now know that many of these are not additive, making the landscape of phenomena in the quantum case much richer; also, it seems to make it much more difficult to evaluate these quantum capacities. The same goes for entanglement measures. After the dramatic progress of Hastings, Smith and Yard, and others, from a couple of years ago, I will here report on the entanglement of purification (EoP) [Terhal et al., JMP 43:4286 (2002)], which measures the total amount of correlation needed to prepare a state. In joint work with Jianxin Chen (IQC Waterloo) we show strong evidence that EoP is not additive, although it is known to be additive for certain families of states. (hide abstract) Abstract:The reversible evolution of a quantum system among alternative states, such as the up and down states of a spin-1/2, cannot be described as a classical Markov process among a finite number of classical configurations. Indeed, a Markov process always relaxes into a stationary probability distribution. In this talk, I present a stochastic classical model with time-correlated noise that reproduces exactly the dynamics of a qubit between two consecutive measurements. The time correlation of the noise guarantees the reversibility of the evolution. The invasiveness of a measurement is accounted for by the updating of a single classical bit. The case of multiple measurements is also discussed and a novel experimental test of quantum mechanics is proposed. I then show the relation of this model with the Toner-Bacon model, which classically simulates the communication of a qubit through the communication of two classical bits. Finally, I discuss the generalization of the stochastic model to the case of many qubits. (hide abstract) Abstract:The theorem of Wigner, Araki and Yanase (WAY) demonstrates that there are constraints to quantum measurements when there is an additive conserved quantity (on the Hilbert space of the system and measuring apparatus) that does not commute with the observable we wish to measure. The original theorem applied only to a restricted class of observables and conserved quantities. I'll review this theorem and discuss some generalisations, in particular to the case of position measurements which respect the conservation of linear momentum. I'll also talk about the notion of ``relative'' observables and reference frames within the context of the WAY theorem. (hide abstract) Abstract:We present explicitly computable POVMs for detecting the true state among a finite number of hypothetic states of a given quantum system. Our algorithm mimics the classical maximum likelihood method. In particular, it recovers the classical decision rule in the special case of commuting states. Moreover, it generalizes a recent construction for multiple pure states. If applied to n copies of the basic quantum system, the resulting detectors feature an optimal exponential decay of the averaged error probability for a large class of mixing states: The asymptotic error exponent is given by the multiple quantum Chernoff bound of the set of states. Further, we outline a modification which universally attains the bound up to a factor 1/3. References: 1. Nussbaum, M. and Szkola, A. "Asymptotically optimal discrimination between multiple pure quantum states." In: Theory of Quantum Computation, Communication and Cryptography. 5th Conference, TQC 2010, Leeds, UK. Lecture Notes in Computer Science, Vol 6519, pp. 1-8, Springer (2011) 2. Nussbaum, M. and Szkola, A. "An asymptotic error bound for testing multiple quantum hypotheses", accepted for publication in Ann. Statist. (2011) (hide abstract) Abstract:I will discuss two recent approaches to the quantification of entanglement and quantum correlations, one based on a principle of minimally perturbing local unitary operations and their global effects, the other generalizing the concept of global geometric entanglement to the bipartite case. Following these approaches, one can identify bona fide distance measures of pure-state entanglement and mixed-state quantumness. I will briefly review some applications, with special emphasis on the quantification of frustation in collective quantum systems. (hide abstract) Abstract:The von Neumann entropy is one of the most important quantities in quantum information theory. Often of use to us are the inequalities which govern how large the entropies of different subsystems can be in relation to each other. The famous result of strong subadditivity is one such inequality, which underpins all the other known inequalities. I will present a new, infinite family of inequalities which are independent of strong subadditivity, and of each other. However, these inequalities are constrained, in the sense that they must hold only when certain instances of strong subadditivity hold with equality. (hide abstract) Abstract:In previous work, we have shown that successful complexity analysis of unconventional computers requires an approach different from that employed in the standard, Turing-machine case; notably for the paradigm's timeliness and importance, this is true of the quantum computer. We recap from previous research a model-independent framework of complexity theory (which, of course, accommodates quantum computation), mention from immanent research an application of the framework to Shor's algorithm, and describe from proposed research an extension of the framework from complexity-theoretic to cryptographic concerns. (hide abstract) Abstract:In many fundamental problems of information theory and statistics, the efficiency of an asymptotically optimal protocol can be expressed by the relative entropy of certain states, or some derived quantity of it (entropy, conditional entropy, mutual information, etc.). In a more detailed analysis of these protocols, e.g., in the study of the exact decay rates of the relevant error probabilities, the efficiency is usually characterized by a Renyi relative entropy or a related quantity (like the Chernoff and the Hoeffding distances). In this talk I demonstrate the central importance of the Renyi relative entropies through a number of problems, including the discrimination of correlated quantum states, data compression, classical-quantum channel coding and the reversibility of quantum operations. (hide abstract) Abstract:If quantum information has done anything, it has truly highlighted the power of quantum correlations as resources for information processing. Quantum correlations also exhibit significantly non-classical behaviour by potentially violating Bell inequalities. Bell inequalities put constraints on the correlations of space-like separated measurements in classical, or more generally, local hidden variable (LHV) theories and thus provide a clear separation between classical and non-classical with few assumptions. Despite the paucity of assumptions, they have still been difficult to implement completely in the lab resulting in so-called loopholes that allow LHV theories to simulate quantum correlations. For example, loopholes can arise if measurements are imperfect and involve post-selection or are not space-like separated. Bell inequalities have also been used quite extensively in information processing tasks, e.g. quantum key distribution for cryptography and generating random numbers. We consider Bell inequalities from a computational point-of-view. We demonstrate that constructing LHV correlations in a multi-partite Bell inequality setting has a simple and elegant computational interpretation. What is more, this scenario can be mapped into a subset of computations in Measurement-based Quantum Computing (a model of quantum computing where single-qubit measurements are performed on an entangled state). However, full Measurement-based Quantum Computing requires measurements to be time-ordered and adaptive whereas space-like separation rules this out in Bell inequality experiments. We propose a method of post-selection that simulates full Measurement-based Quantum Computing without leading to the troublesome loopholes mentioned above. Remarkably this post-selection actually strengthens quantum correlations in Bell inequality experiments. Therefore, not only can we consider links between quantum computation and non-classical correlations, we motivate the foundational study of multi-partite quantum correlations. (hide abstract) Abstract:This talk, based on a joint work with M. Tomforde and V. Paulsen, will be concerned with quantisations of ordered *-vector spaces. Given an Archimedean ordered *-vector space, I will describe the minimal and the maximal operator system structures with which it can be equipped, as well as their universal properties. A description of the entanglement breaking maps on the space of n by n matrices will then be given in terms of these extremal operator system structures. (hide abstract) Abstract:"Frustration" in many-body systems occurs when the ground state of a many-body system cannot simultaneously minimize the energy of all its local interactions. It plays a key role in the physics of many condensed matter systems, such as spin models or even water ice. Indeed, it was first studied by Pauling, who showed that the anomalous experimental value for the zero-temperature entropy of ice is caused by frustration in the position of the oxygen atom in the crystal lattice. Since it can play an important role in determining physical properties, we would like to know which condensed matter systems are frustrated, and which are frustration-free. More precisely, given a many-body Hamiltonian, we would like to know whether its ground state is frustrated or not. It turns out that this question is impossible to answer. We show that even for a translationally-invariant, 1-dimensional spin chain, with two-body interactions described by a Hamiltonian with a fixed, finite dimension, determining whether the ground state is frustrated is uncomputable (in the halting problem sense). (Joint work with Michael Wolf and David Perez-Garcia) (hide abstract) Abstract:This talk will be followed by another talk entitled: A system equilibrates when diagonalizing its hamiltonian is difficult (hide abstract) Abstract:We study scenarios where a finite set of non-demolition von-Neumann measurements are available. We note that, in some situations, repeated application of such measurements allows estimating an infinite number of parameters of the initial quantum state, and illustrate the point with a physical example. We then move on to study how the system under observation is perturbed after several rounds of projective measurements. While in the finite dimensional case the effect of this perturbation always saturates, there are some instances of infinite dimensional systems where such a perturbation is accumulative, and the act of retrieving information about the system increases its energy indefinitely (i.e., we have âHeat Visionâ). We analyze this effect and discuss a specific physical system with two dichotomic von-Neumann measurements where Heat Vision is expected to show. (hide abstract) Abstract:We devise a protocol in which general non-classical multipartite correlations produce a physically relevant effect, leading to the creation of bipartite entanglement. In particular, we show that the relative entropy of quantumness, which measures all non-classical correlations among subsystems of a quantum system, is equivalent to and can be operationally interpreted as the minimum distillable entanglement generated between the system and local ancillae in our protocol. We emphasize the key role of state mixedness in maximizing non-classicality: Mixed entangled states can be arbitrarily more non-classical than separable and pure entangled states. (hide abstract) Abstract:We introduce a universal measure of frustration for quantum systems and provide sharp lower bounds for it in terms of a class of entanglement monotones. We identify sufficient conditions for a spin-1/2 system to saturate these bounds and show how they represent a quantum generalization of the Toulouse criterion for classical frustration-free systems. Our analysis provides a unifying scheme for studying entanglement and frustration in quantum systems and shows how the relation among these is dictated by the presence or absence of geometric frustration. (hide abstract) Abstract:Operationally, the strong capacity of a particular channel can be interpreted as a limit on the amount of information which can be transmitted reliably over that channel. To evaluate the (strong) capacity of a particular channel one must prove both the direct part of the channel coding theorem and strong converse for the channel. We consider the strong converse theorem for the periodic quantum channel and show that the strong converse does not hold for it; therefore, this channel does not have a strong capacity. (hide abstract) Abstract:The field of communication complexity studies the amount of communication between two parties that is needed for them to compute some function of their distributed inputs. The model of one-way communication is of particular interest due to its simplicity, conceptual appeal and many applications. In this talk, I will discuss a new example of a partial function whose one-way quantum communication complexity is significantly lower than its one-way classical communication complexity. The proof uses Fourier analysis on the boolean cube. The talk is based on the paper arXiv:1007.3587. (hide abstract) Abstract:The purpose of this talk is to show the existence of a pair of two-qubit states such that any number of copies of one state or the other cannot violate the CHSH Bell inequality. However, their tensor product, by measuring suitably chosen operators, can produce a CHSH violation of at least 2.023. We also identify a CHSH-local state such that two copies of it are CHSH-violating. The tools employed here consist of symmetric extension of quantum states and the see-saw iteration method, which can be easily adapted to find instances of nonlocality activation in arbitrary Bell scenarios. This talk is based on a joint work with Miguel NavascuÃ©s. (hide abstract) Abstract:It is natural in physics to measure the Ã¢ÂÂcorrelationÃ¢ÂÂ between two quantum physical systems using the correlation between the outcomes of measurements on those two systems. However the maximum correlation between measurement outcomes can still drastically underestimate the quantum correlations present. We quantify the distinction between classical and quantum correlations by demonstrating that after removing a logarithmic-sized quantum system from one half of a pair of perfectly correlated bitstrings, even the most sensitive pair of measurements might only yield outcomes essentially independent of each other. In another sense, we demonstrate that the classical mutual information can be arbitrarily small for a receiver decoding the logarithmically incomplete bitstring, a setting known as locking. However, we also show that with access to the complete quantum system, the receiver can decode the bitstring nearly perfectly. We thus call the logarithmic-sized region between the two settings the "locking-decoding frontier". Moreover, we find that this locking property is generic, in the sense that it occurs when removing a random subsystem. As such, the effect might be relevant to statistical mechanics or black hole physics. We assume only a min-entropy bound on the message and also explore the effect of entanglement on the width of the frontier. (hide abstract) Abstract:The Bell-Kochen-Specker theorem proves the impossibility of a classical hidden variable theory that would explain the quantum mechanical predictions on a single system, at least if the classical theory is "non-contextual". In the talk i will review the basic argument, and discuss recent ideas to test quantum contextuality in experiments, via so- called non-contextual inequalities. These inequalities, starting with the work of Klyachko et al., exhibit a rich combinatorial structure relating to topics in graph theory. I will also discuss which hidden variable theories are ruled out by actual experiments, in the light of the recent "finite precision" debate initiated by Meyer, Kent and Clifton. [Partly based on joint work with Adan Cabello and Simone Severini, arXiv:1010.2163] (hide abstract) Abstract:Multipartite entanglement is not only a key feature of complex many-body quantum systems- it also constitutes a fundamental resource in quantum information processing. Especially in large and high dimensional systems full state tomography and thus complete information about the state of a system is experimentally inaccessible. We therefore need methods of detecting, classifying and possibly quantifying multipartite entanglement that scale favorably with system size. We present such a framework and show that it can be utilized to explore the phenomenon of genuine multipartite entanglement in various ways. We explicitly discuss the effect of noise and experimental imperfection in exemplary cases, demonstrating the strength of the presented criteria. (hide abstract) Abstract:We show that the noncontextual inequality proposed by Klyachko et al. [Phys. Rev. Lett. 101, 020403 (2008)] belongs to a broader family of inequalities, one associated to each compatibility structure of a set of events (a graph), and its independence number. These have the surprising property that the maximum quantum violation is given by the LovÃÂ´asz #-function of the graph, which was originally proposed as an upper bound on its Shannon capacity. Furthermore, probabilistic theories beyond quantum mechanics may have an even larger violation, which is given by the so-called fractional packing number. We discuss in detail, and compare, the sets of probability distributions attainable by noncontextual, quantum, and generalized models; the latter two are shown to have semidefinite and linear characterizations, respectively. The implications for Bell inequalities, which are examples of noncontextual inequalities, are discussed. In particular, we show that every Bell inequality can be recast as a noncontextual inequality `a la Klyachko et al. (hide abstract) Abstract:I'll give an overview of Mutually Unbiased bases discussing their construction and use in quantum information tasks such as state tomography, uncertainty relations and quantum cryptography. I'll also talk about the conjectured non-existence of complete sets in dimensions such as six. I'll review the attempts to prove the conjecture and talk about some open problems. (hide abstract) Abstract:Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. A natural generalization of constraint satisfaction problems to the quantum setting is the local Hamiltonian problem, which is of significant interest to both complexity theorists and to physicists studying properties of physical systems alike. In this talk, we define a natural approximation version of the local Hamiltonian problem and initiate its study. We present two main results. The first shows that a non-trivial approximation ratio can be obtained in the class NP using product states. The second result, which builds on the first one, gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the Ã¢ÂÂexhaustive sampling methodÃ¢ÂÂ by Arora et al. [J. Comp. Sys. Sci., vol. 58, 1999] to the quantum setting, and might be of independent interest. This talk is based on joint work with Julia Kempe. (hide abstract) Abstract:Decoherence happens when information about a quantum system irreversibly spreads to its environment. It is believed that this phenomenon is responsible for the emergence of classical kinematics and dynamics. Given a quantum system and an appropriate description of its environment, how can one derive the classical apparence of that system, if any? This question appears to be very difficult to answer from the traditional approach to this problem in which one simply ignores the information content of the environment. Instead, we explore the hypothesis that the classical effective theory is precisely a description of that information. We consider a simple model which is equivalent to a continuous monitoring of the quantum system by the environment. Hence the emergent classical dynamical theory has the form of a probability distribution over histories. We apply this method to a relativistic scalar field using the path integral formalism. (hide abstract) Abstract:Why do closed macroscopic systems equilibrate and thermalize? How can we justify the methods of thermodynamics and statistical mechanics from a microscopic theory? Which mechanisms lead to the emergence of classical, statistical behaviour and decoherence? In this talk, I show (i) how standard quantum mechanics without added randomness can explain the phenomenon of equilibration despite its unitary time development, and (ii) that an arbitrary weak interaction with an environment causes decoherence in the local energy eigenbasis. (hide abstract) Abstract:We discuss the family of operator norms recently investigated in [1] and some of their implications in quantum information. We referred to these norms as Schmidt norms since they derive from the Schmidt decomposition theorem for quantum states.These norms find applications to central problems in quantum information, including the problem of determining k-positivity of linear maps (and thus detecting k-entanglement witnesses) and finding bound entangled non-positive partial transpose states. References: [1] N. Johnston and D. W. Kribs, Schmidt Norms for Quantum States. Preprint (2009). arXiv:0909.3907v2 [quant-ph] (hide abstract) Abstract:I'll talk about some new results on efficiently simulating Hamiltonians. I'll start with the problem of simulating sparse Hamiltonians, current approaches to the problem and the best known approach today for simulating sparse Hamiltonians to high precision. Then I'll discuss the problem of simulating dense Hamiltonians, and present some results which suggest that known simulation methods based on quantum walks cannot be improved dramatically. This talk is based on two papers, arXiv:0908.4398 and arXiv:1003.3683. This is joint work with Andrew Childs. (hide abstract) Abstract:What distinguishes quantum theory from other general no-signaling theories, i.e., those where no instantaneous communication is allowed? In this talk, I will present the 'Guess your Neighbour's input' game, where each player must guess the input-bit received by his neighbour. For more than 2 players, having classical and quantum resources always leads to the same maximum winning probability, but other no-signaling resources can do better. Moreover, some of the Bell inequalities associated to this game correspond to facets of the local polytope. Then, it identifies parts of the boundary between quantum and post-quantum correlations of maximal dimension. Such results provide the first game to distinguish quantum correlations from stronger no-signaling correlations in the multipartite scenario. In addition, since the game is naturally associated to signaling, it suggests that quantum correlations might obey a generalization of the usual no-signalling conditions in a multipartite setting. (hide abstract) Abstract:We analyze Navascues-Pironio-Acin work [NJP 10, 073013 (2008)] and find an intriguing statistical interpretation of the results. Using this we suggest that quantum formalism can be derived from first principles. Namely, any theory in which a global statistical picture is achievable is consistent with quantum theory. Counter intuitively this principle does not contradict contextuality proofs of quantum theory in the limit of weak measurements. This work also enables unifying Bell inequalities and Leggett-Garg inequalities in a single framework. (hide abstract) Abstract:Matrices have a double life: algebraic and combinatorial. The pattern formed by the positions of the zeros is an aspect of their combinatorial life. Despite I am not a matrix, it is also an aspect of my life, since the topic ended up to be part of my PhD research -- here, in the Alma Mater Bristol. This talk is a medley of young notions and results about patterns of zeros in matrices. In particular, I will consider orthogonal matrices and semidefinite rank problems, and I will discuss combinatorial parameters like the Colin de Verdiere and the Lovasz number. Some of the ideas linked with quantum information will be highlighted. (hide abstract) Abstract:We introduce two relative entropy quantities called the min- and max-relative entropies and discuss their properties and operational meanings. These relative entropies act as parent quantities for optimal one-shot rates of information-processing tasks such as data compression, information transmission and entanglement manipulation. Moreover, they lead us to define entanglement monotones which have interesting operational interpretations. (hide abstract) Abstract:We propose a realistic protocol to generate entanglement between quantum memories at neighboring nodes in hybrid quantum repeaters. Generated entanglement includes only one type of error, which enables efficient entanglement distillation and entanglement swapping. In contrast to the known protocols with such a property, our protocol with ideal detectors achieves the theoretical limit of the success probability and the fidelity to a Bell state, promising higher efficiencies in the repeaters. We also show that the advantage of our protocol remains even with realistic threshold detectors. This talk will be based on two papers: [1] Phys. Rev. A *80*, 060303(R) (2009); [2] arXiv: 0908.2735 (to be published in Phys. Rev. A). (hide abstract) Abstract:Reference: D. Jennings and T. Rudolph, http://arxiv.org/abs/1002.0314 This talk will be about the types of "weird" processes that can occur - in particular heat flow from hotter to colder bodies - when systems and reservoirs (either classical or quantum) are correlated, contrary to the standard thermodynamic assumption of no initial correlations (i.e "molecular chaos"). It was motivated by Partovi's example of such a violation of the thermodynamic arrow, presented in [1] that he claimed was a manifestation of entanglement. It turns out that Partovi's example requires only classical correlation between the system and reservoir, and our motivation was to find out the difference between the case of initial quantum versus classical correlations. We show how to use the mutual information as a way of quantifying the amount of "negative heat flow", and show that the amount of such a flow can be larger for the case of initial entanglement, in some sense providing an entanglement witness different to those considered previously. I will also discuss Maccone's proposed "quantum resolution to the arrow of time"[2], and explain why it is flawed [3]. I regret this talk will not be as crazy as one would hope for from a talk with such a title. An indication of this is I will briefly mention some simple experiments that could be performed on small numbers of qubits to illustrate the main ideas. [1] H. Partovi, Phys. Rev. E 77, 021110 (2008), [2] L. Maccone, Phys. Rev. Lett. 103 080401 (2009) [3] D. Jennings and T. Rudolph, arxiv.org/abs/0909.1726 (hide abstract) Abstract:We extend Wielandt's inequality to quantum channels. That is, we find upper bounds to the number of times a channel must be applied so that it maps any density operator to one with full rank. Using this bound we derive dichotomy theorems for the zero-error capacity of quantum channels and for the Matrix Product State (MPS) dimension of ground states of frustration free Hamiltonians. The obtained inequalities also imply new bounds on the required interaction-range of Hamiltonians with unique MPS ground state. (hide abstract) Abstract:I will develop a concept of entanglement percolation for long-distance singlet generation in quantum networks where neighbouring nodes are connected by partially entangled bipartite mixed states. I will give a necessary and sufficient condition on the class of mixed network states for the generation of singlets. I will discuss that neighbouring nodes are required to be connected by multiple partially entangled states to achieve entanglement percolation. Furthermore I will devise a rich variety of distillation protocols for the conversion of these mixed states into singlets. Finally, I will introduce possible further improvements achievable by using quantum strategies including generalized forms of entanglement swapping. (hide abstract) Abstract:After a short introduction on anyons and quantum walks we shall present the one dimensional quantum walk of anyonic systems. The anyonic walker performs braiding operations with stationary anyons of the same type ordered canonically on the line of the walk. Abelian as well as non-Abelian anyons are considered that exhibit dramatically different behaviours. The relation between walker position and Jones polynomials, topological invariants of links and knots, is established. (hide abstract) Abstract:Unlike classical information, quantum information can be present in more than one "type", and various types can be incompatible (e.g. the information represented by the X component of a spin one-half particle versus its Z component counterpart). In this talk I will introduce the notion of "type of information" and I will demonstrate how to use this concept to study the location of quantum information in arbitrary carrier subsets of additive graph codes. To various types of information we associate a collection of operators on the coding space which form what we call the information group. It represents the input information through an encoding operation constructed as an explicit quantum circuit. Partial traces of these operators down to a particular subset of carriers provide an isomorphism of a subgroup of the information group, and this gives a precise characterization of what kinds of information they contain. All carriers are assumed to have the same dimension D, an arbitrary integer greater than 1 (not necessarily prime). The talk will be pedagogical and will be accompanied by a series of illustrative examples. No special pre-requisites are required. For a detailed discussion the interested reader can consult our work at arXiv:0912.2017 [quant-ph]. (hide abstract) Abstract:The measurement based or cluster state quantum computer is a scheme which is universal for quantum computing. Measurments are performed on a highly entangled 2 or 3 dimensional lattice, with the result of one measurment determining the basis for the next. In such a scheme the generation of entanglement is pushed offline which means any errors in this process can be corrected before calculations take place. In this talk I will introduce a deterministic method of generating cluster states using a qubus architecture. This architecture uses a continuous variable field to generate entanglement between the qubits, in this case the C-Phase gates required to generate a cluster state. The method I present for generating cluster states is dynamic allowing the cluster state to be grown in one dimension to any desired size. I show that my method shows a dramatic improvement over a naive method of cluster state generation using the qubus and an improvement over previous work also showing an improvement. (hide abstract) Abstract:The zero-error classical capacity of a quantum channel is the asymptotic rate at which it can be used to send classical bits perfectly, so that they can be decoded with zero probability of error. The study of zero-error capacities dates right back to Shannon and the early days of information theory. We show that there exist pairs of quantum channels, neither of which individually have any zero-error capacity whatsoever (even if arbitrarily many uses of the channels are available), but such that access to even a single copy of both channels allows classical information to be sent perfectly reliably. In other words, we prove that the zero-error classical capacity can be superactivated. This result is the first example of superactivation of a classical capacity of a quantum channel. We then strengthen this result to show that there exist pairs of channels, neither of which have any zero-error classical capacity (as before), yet for which access to a single copy of the joint channel even allows far more delicate quantum information to be transmitted perfectly. This subsumes the first result, and it also implies that the quantum zero-error capacity can be superactivated. Indeed, these channels exhibit superactivation of both their classical and quantum zero-error capacities simultaneously. This is the strongest conceivable form of superactivation, and nothing similar is possible for standard Shannon capacities of quantum channels or for zero-error capacities of classical channels. We term this striking effect "super-duper-activation". (hide abstract) Abstract:Consider a quantum system composed of N+1 particles. How does one of the particles of the system (now promoted to the role of a "quantum observer") describe the joint state of the other N particles? In this work we investigate fundamental questions emerging in this scenario. We uncover a paradox in which an arbitrarily distant particle is found to dramatically influence the physics in the vicinity of the quantum observer. In solving the puzzle some crucial features of quantum reference frames are identified. (hide abstract) Abstract:Given one or more uses of a classical channel, only a certain number of messages can be transmitted with zero probability of error. The study of this number and its asymptotic behaviour constitutes the field of classical zero-error information theory, the quantum generalisation of which has started to develop recently. We show that, given a single use of certain classical channels, entangled states of a system shared by the sender and receiver can be used to increase the number of (classical) messages which can be sent with no chance of error. In particular, we show how to construct such a channel based on any proof of the Bell-Kochen-Specker theorem. This is a new example of the use of quantum effects to improve the performance of a classical task. We investigate the connection between this phenomenon and that of ``pseudo-telepathy'' games. The use of generalised non-signalling correlations to assist in this task is also considered. In this case, a particularly elegant theory results and, remarkably, it is sometimes possible to transmit information with zero-error using a channel with no unassisted zero-error capacity. (hide abstract) Abstract:Quantum particles have the ability to be very strongly correlated, a phenomenon called entanglement. In my talk I will explain how the presence of quantum correlations can assist in performing "impossible" computational tasks [1]. I will then show how quantum correlations can be used to "remote control" any quantum system, with the help of a single auxiliary qubit [2]. While these are man made, externally controlled applications of quantum correlations one may wonder if existing natural processes exploit their power. I will show how quantum correlations can help "squeeze" energy in many physical situations by forcing collective behaviour. Finally, I would like to debate with you, if a single massive Boson that occupies a confined volume results in spatial regions of the volume to be entangled and how this may be tested with a Bell-inequality [3]. References: [1] J. Anders, D. E. Browne, Phys Rev Lett 102 050502 (2009). [2] J. Anders, D.K.L. Oi, E. Kashefi, D.E. Browne, E. Andersson, arXiv:0911.3783v1 (2009). [3] L. Heaney, J. Anders, Phys Rev A 80 032104 (2009). (hide abstract) Abstract:The spontaneous emission of photons from optical cavities and from individually trapped atoms has been studied extensively in the framework of quantum optics. Theoretical predictions based on the rotating wave approximation (RWA) are in general in very good agreement with experimental findings. However, current experiments aim at combining better and better cavities with large numbers of tightly confined atoms. Here we predict an energy concentrating mechanism in the behavior of such a composite quantum system which cannot be described by the RWA. Its result is the continuous leakage of photon through the cavity mirrors even in the absence of external driving and even when there are initially no photons inside the resonator. We finally discuss the predicted phenomenon in the context of thermodynamics. (hide abstract) Abstract:In order to categorise and quantify the types and amount of entanglement that we might find in real physical systems (described by local Hamiltonians), we discuss these issues for the thermal states of graphs. After a brief review of the distillability properties of these graphs, we calculate the critical temperatures for the persistence k-partite bound entanglement phases present in this model for a restricted class of graphs including, for example, the 1D cluster state. (hide abstract) Abstract:Quantum mechanical uncertainty relations provide bounds on the minimum uncertainties about the outcomes of two alternative measurements applied to the same quantum state. In this paper, we prove an entropic uncertainty relation which, in contrast to known such relations, is valid in the context of quantum side information. It strengthens and extends the entropic uncertainty relation of Maassen and Uffink [Phys. Rev. Lett. 60, 1103 (1988)] and also implies an inequality recently conjectured by Boileau and Renes [Phys. Rev. Lett. 103, 020402 (2009)].The proof uses the formalism of smooth quantum entropies. (hide abstract) Abstract:Many important theorems in quantum information theory can be proven in a particularly simple manner by showing that two quantum systems are "decoupled" (meaning that they are in a product state). In this talk, I will present a theorem that generalizes most of the methods that are used to show that two systems are decoupled. This yields simplified and more direct proofs of the correctness of many protocols. (hide abstract) Abstract:We consider the implementation of two-party cryptographic primitives based on the sole assumption that no large-scale reliable quantum storage is available to the cheating party. We construct novel protocols for oblivious transfer and bit commitment, and prove that realistic noise levels provide security even against the most general attack. Such unconditional results were previously only known in the so-called bounded-storage model which is a special case of our setting. Our protocols can be implemented with present-day hardware used for quantum key distribution. In particular, no quantum storage is required for the honest parties. Joint work with Robert Koenig and Juerg Wullschleger (hide abstract) Abstract:I will discuss an alternative formulation of the problem of quantum optical fields in a curved space-time inspired by quantum mechanical consistency requirements in exotic metrics. I will contrast this new formulation with the standard approach and find observable differences for entangled states. I will propose an experiment in which an entangled pair of optical pulses are propagated through non-uniform gravitational fields and find that the new formulation predicts de-correlation of the optical entanglement under experimentally realistic conditions. (hide abstract) Abstract:Suppose Alice and Bob make local two-outcome measurements on a shared entangled state. For any d, we show that there are correlations that can only be reproduced if the local dimension is at least d. This resolves a conjecture of Brunner et al. and establishes that the amount of entanglement required to maximally violate a Bell inequality must depend on the number of measurement settings, not just the number of measurement outcomes. We prove this result by establishing the first lower bounds on a new generalization of Grothendieck's constant. Joint work with Jop Briet and Ben Toner (hide abstract) Abstract:What is probability in Quantum Mechanics? Considering this conceptual problem, a weak value may be a useful tool to discuss the mathematical property of the probability space. Furthermore, the weak value of an observable is experimentally accessible by weak measurements as theoretically analyzed by Aharonov et al. and recently experimentally demonstrated. We introduce the weak operator associated with the weak value and give a general framework of quantum operations to the weak operator in parallel with the Kraus representation of the completely positive map for the density operator. The decoherence effect is also investigated in terms of the weak measurement by a shift of a probe wave function of continuous variable [1]. In this talk, we introduce the weak value from the view of the probability space and a new technique to get the weak values from the analogy of the quantum eraser [2]. Finally we discuss the general framework of the weak values with decoherence. [1] Y. Shikano and A. Hosoya, arXiv:0812.4502. [2] S. Tamate, H. Kobayashi, T. Nakanishi, K. Sugiyama, and M. Kitano, arXiv:0906.0212. (hide abstract) Abstract:Using new results on the separability properties of bosonic systems, we provide a new complete criterion for separability. This criterion aims at characterizing the set of separable states from the inside by means of a sequence of efficiently solvable semidefinite programs. We apply this method to derive arbitrarily good approximations to the optimal measure-and-prepare strategy in generic state estimation problems. Finally, we report its performance in combination with the criterion developed by Doherty et al. [1] for the calculation of the entanglement robustness of a relevant family of quantum states whose separability properties were unknown. [1] A. C. Doherty, P. A. Parrilo, F. M. Spedalieri, Phys. Rev. Lett. 88, 187904 (2002). (hide abstract) Abstract:By popular demand I'm going to present the details of the paper arXiv:0905.2292. With respect to a nonlocal game based on the idea of random access codes, I will show that quantum theory obeys a certain information inequality - which we dubbed "information causality" in the paper. Assuming this relation, one can then derive Tsirelson's bound on the CHSH correlator, and also recover other bounds on the quantum region within the non-signalling polytope. The question arises whether by adopting information causalty as a fundamental (intuitive?) principle, one can recover the predictions of quantum theory in all non-signalling contexts. (hide abstract) Abstract:Single-particle quantum theory with fundamental indeterminacy based on complex probability amplitudes undergoing linear superposition principle is an inevitable consequence of special relativity with the principle of relativity extended to superluminal observers. (hide abstract) Abstract:We attempt at characterizing the correlations present in the quantum computational model DQC1, introduced by Knill and Laflamme [Phys. Rev. Lett. 81, 5672 (1998)]. The model involves a collection of qubits in the completely mixed state coupled to a single control qubit that has nonzero purity. Although there is little or no entanglement between two parts of this system, it provides an exponential speedup in certain problems. On the contrary, we find that the quantum discord across the most natural split is nonzero for typical instances of the DQC1 ciruit. Nonzero values of discord indicate the presence of nonclassical correlations. We propose quantum discord as figure of merit for characterizing the resources present in this computational model. This might be a complementary measure for counting resources in quantum information science. (hide abstract) Abstract:Frustration-free hamiltonians, i.e. hamiltonians whose ground state is locally a ground state for each interaction term, arise in a variety of applications in condensed matter physics and quantum information theory. Examples include the AKLT model and Rokhsar-Kivelson models in condensed matter physics and quantum satisfiability in quantum information theory. Due to the absence of frustration in these systems it is tempting to conjecture that all frustration-free systems can also be solved locally and efficiently (i.e., using only a polynomial number of arithmetic operations in the number of quantum spins). In this talk I'll show for a large class of such systems that this is indeed the case. I'll also review a class of frustration-free systems in 1D which provably cannot be solved efficiently. (hide abstract) Abstract:Random unitaries are very useful things with many applications. There are many results that say a unitary picked at random will have desirable properties with high probability. However, these results are not very physically or computationally relevant because random unitaries cannot be constructed efficiently. In this talk, I take a pseudo-random set of unitaries (called a k-design) that can be efficiently constructed and show that in many cases the desirable properties of truly random unitaries can be reproduced. I will then illustrate this with examples, including showing that pseudo-random unitaries are enough to give the 'principle of equal a priori probabilities' from statistical mechanics, in the sense of Popescu, Short & Winter, Nature Physics (2006). (hide abstract) Abstract:Would you believe that all the claims of "unconditional security" made prior to the year 2007, both by theorists and experimentalists, were valid only under the assumption that the secret key is of *infinite length*? A few people were actually aware of the problem, but the mathematical complexity of the task seemed beyond reach. Then came Renato Renner, who invented all the tools in his thesis. It just needed someone to dig out the meaningful formulas, put them in Matlab and compute numbers --- and this is the kind of task even the present speaker can contribute to :-) The result was shocking for many: you cannot extract any secret key at all unless you process 10^5 or 10^6 signals (you guess it: very few experiments, if any, complied). The asymptotic bounds are recovered only when the number of signals goes beyond 10^10, which is simply beyond reach. In this short talk, I shall show how the finite-key security bound looks ultimately very natural, and present in detail some of the results for the BB84 protocol in various implementations. (hide abstract) Abstract:We introduce variants of relative entropy of entanglement based on the optimal distinguishability from unentangled states by means of restricted measurements. In this way, we are able to prove that the standard regularized entropy of entanglement is strictly positive for all multipartite entangled states. In particular, this implies that the asymptotic creation of a multipartite entangled state by means of local operations and classical communication always require the consumption of a non-local resource at a strictly positive rate. (hide abstract) Abstract:Valiant-Vazirani showed in 1985 that solving NP with the promise that "yes" instances have only one witness is powerful enough to solve the entire NP class (under randomized reductions). We are interested in extending this result to the quantum setting. We prove extensions to the classes Merlin-Arthur (MA) and Quantum-Classical-Merlin-Arthur (QCMA). Our results have implications on the complexity of approximating the ground state energy of a quantum local Hamiltonian with a unique ground state and an inverse polynomial spectral gap. We show that the estimation, to within polynomial accuracy, of the ground state energy of poly-gapped 1-D local Hamiltonians is QCMA-hard, under randomized reductions. This is in strong contrast to the case of constant gapped 1-D Hamiltonians, which is in NP. Moreover, it shows that unless QCMA can be reduced to NP by randomized reductions, there is no classical description of the ground state of every poly-gapped local Hamiltonian which allows the calculation of expectation values efficiently. Finally, we discuss a few obstacles towards establishing an analogous result to the class Quantum-Merlin-Arthur (QMA). In particular, we show that there is no black box reduction, micking the construction of valiant and Vazirani, in the quantum case. This is joint work with Dorit Aharonov, Michael Ben-Or and Or Sattath. (hide abstract) Abstract:Many computational problems can be recast in terms of whether some initial entangled state can be transformed into another by local operations and classical communication. While the problems may appear completely unrelated, they share a common mathematical structure and thus the same set of necessary and sufficient conditions. In this talk, I will discuss a few examples of problems that can be solved by analyzing bipartite/tripartite entanglement conversions and vice versa. These examples include the bipartite matching problem and the calculation of tensor rank. (hide abstract) Abstract:I will present a quantum algorithm to solve sparse systems of nonlinear differential equations. The algorithm is nondeterministic and its expected resource requirements are poly-logarithmic in the number of variables and exponential in the integration time. The best classical algorithm runs in a time scaling linearly with the number of variables, so this provides an exponential improvement. (hide abstract) Abstract:I will discuss the indirect estimation of Hamiltonian parameters through measuring a few qubits of a large coupled graph. This can be seen as an instance of system identification. Then I will speak about the controllability of the graph through restricted operations on a few qubits. The two problems have a joint graph-theoretical criterion. (hide abstract) Abstract:In this talk I will introduce the notion of 'blind quantum computation'. This term refers to the problem of allowing Alice to have Bob carry out a quantum computation for her such that Bob learns nothing about the computation that he performs. I will briefly review a protocol for accomplishing this task securely, which we presented in arXiv:0807.4154, before discussing the communications complexity of blind quantum computing in general. A generalisation of our original protocol can be shown to have optimal scaling of the required quantum communication. (hide abstract) Abstract:I will talk about implementing the analogue of entanglement swapping in a generalised probabilistic setting (PR boxes). This will require a new concept, that of genuine boxes. I will motivate this and show how it leads to a working non-locality swapping protocol. Finally, I will discuss a surprising, and still mysterious, connection to quantum mechanics. (hide abstract) Abstract:Given a matrix A and a vector b as input, I will describe a quantum algorithm for finding a vector x satisfying Ax=b. The answer is given not as a list of numbers, but as a quantum state |x> that is proportional to the vector x. The run-time scales with the log of the dimension of A, as well as polynomially with the desired accuracy, the sparsity of A (number of nonzero entries per row) and its condition number (ratio between largest and smallest singular values). I will also review classical algorithms for this problem and give a proof that, relative to an oracle, such algorithms cannot be substantially improved upon. Thus, for suitable matrices, our algorithm runs exponentially faster than any possible classical algorithm. This is joint work with Avinatan Hassidim and Seth Lloyd. The arxiv version (0811.3071v1) is somewhat out of date. If you want to read it, I suggest either downloading the paper from this link http://www.maths.bris.ac.uk/~csawh/misc/inversion.pdf or waiting until 0811.3071v2. (hide abstract) Abstract:The insight that the world is fundamentally quantum mechanical inspired the development of quantum information theory. However, the world is not only quantum but also relativistic, and indeed many implementations of quantum information tasks involve truly relativistic systems. In this talk I consider relativistic effects on entanglement in flat and curved spacetimes. I will emphasize the qualitative differences to a non-relativistic treatment, and demonstrate that a thorough understanding of quantum information theory requires taking relativity into account. The exploitation of such relativistic effects will likely play an increasing role in the future development of quantum information theory. The relevance of these results extends beyond pure quantum information theory, and applications to foundational questions in cosmology and black hole physics will be presented. (hide abstract) Abstract:Many capacities of a quantum channel are given by expressions that involve asymptotically large number of uses of the channel, thus, there is no a priori reason for the capacities to be continuous. In this talk, we prove that the ability to transmit classical data, private classical data, quantum data with or without free classical communication on the side are all continuous. Joint work with Graeme Smith from IBM TJ Watson Research Center. (hide abstract) Abstract:When a pre and post-selected quantum system interacts weakly with a probe system, the so-called weak value of an observable of the system is imprinted onto the probe. The weak value can take values outside the range of the eigenvalues of the associated observable, and can even be complex. This effect has been studied extensively to investigate the properties of quantum systems in between measurements, in the time symmetric or two-state vector formalism, and has proven to be a fruitful concept in studying foundational issues in quantum mechanics. Taking a more operational approach, the imprinting of weak values can be exploited to perform useful tasks in quantum information theory, such as in quantum communication schemes, in entanglement concentration, and to amplify small optical effects, allowing them to be measured. Nevertheless, this potentially useful effect has remained relatively unexplored. In this talk I will discuss the use of the weak measurement formalism to perform approximate transformations on the probe system, including transformations which cannot be performed by any physically allowed generalised measurement. In particular the weak measurement formalism provides a conceptually simple scheme to probabilistically realise noiseless amplification of quantum optical states. I will discuss some applications of this effect, including continuous variable entanglement concentration and high-fidelity cloning of small amplitude coherent states. Joint work with David Menzies of the University of St Andrews. (hide abstract) Abstract:We examine theoretic architectures and an abstract model for a restricted class of quantum computation, called here instantaneous quantum computation because it allows for essentially no temporal structure within the quantum dynamics. Using the theory of binary matroids, we argue that the paradigm is rich enough to enable sampling from probability distributions that cannot, classically, be sampled from efficiently and accurately. This paradigm also admits simple interactive proof games that may convince a skeptic of the existence of truly quantum effects. Furthermore, these effects can be created using significantly fewer qubits than are required for running Shor's Algorithm. (hide abstract) Abstract:We present a protocol which allows a client to have a server carry out a quantum computation for her such that the client's inputs, outputs and computation remain perfectly private, and where she does not require any quantum computational power or memory. The client only needs to be able to prepare single qubits randomly chosen from a finite set and send them to the server, who has the balance of the required quantum computational resources. Our protocol is interactive: after the initial preparation of quantum states, the client and server use two-way classical communication which enables the client to drive the computation, giving single-qubit measurement instructions to the server, depending on previous measurement outcomes. Our protocol works for inputs and outputs that are either classical or quantum. We give an authentication protocol that allows the client to detect an interfering server; our scheme can also be made fault-tolerant. Our protocol is the first universal scheme which is independent of the properties of the function to be evaluated. This is in contrast with other classical or quantum approaches based on the notion of computing with encoded data, which exploit the properties of the underlying function to derive an efficient encoding and decoding algorithms. However the novelty of our approach is in the using of the unique feature of the measurement-based quantum computing that separates classical and quantum part of computation and will lead to a generic scheme for blind computation of any arbitrary function. (hide abstract) Abstract:In recent years, the analysis of boolean functions has arisen as an important theme in theoretical computer science. In this talk I will discuss an extension of the concept of a boolean function to quantum computation. It turns out that many important classical results in the theory of boolean functions have natural quantum analogues. These include property testing of boolean functions; the Goldreich-Levin algorithm for approximately learning boolean functions; and a theorem of Friedgut, Kalai and Naor on the Fourier spectra of boolean functions. The quantum generalisation of this theorem uses a quantum extension of the hypercontractive inequality of Bonami, Gross and Beckner. This talk is based on joint work with Tobias Osborne. (hide abstract) Abstract:We present a novel quantum tomographic reconstruction method based on Bayesian inference via the Kalman filter update equations. The method not only yields the maximum likelihood/optimal Bayesian reconstruction, but also a covariance matrix expressing the measurement uncertainties in a complete way. From this covariance matrix the error bars on any derived quantity can be easily calculated. This is a first step towards the broader goal of devising an omnibus reconstruction method that could be adapted to any tomographic setup with little effort and that treats measurement uncertainties in a statistically well-founded way. We restrict ourselves to the important subclass of tomography based on measurements with discrete outcomes (as opposed to continuous ones), and we also ignore any measurement imperfections (dark counts, less than unit detector efficiency, etc.), which will be treated in further work. We illustrate the general theory on two real tomography experiments of quantum optical information processing elements. (hide abstract) Abstract:Non-local correlations are a central theme in quantum mechanics and tell us that there exist states in the joint Hilbert space of subsystems that have measurement outcomes not describable by local realism. There is another kind of non-locality arising from topological interactions amoung anyons which is metric independent. I will describe how the later concept can be understood in terms of the former via a Bell like inequality between measurements on the fusion products of the anyons. (hide abstract) Abstract:Recently, the field of linear quantum optics has witnessed for the first time, the successful demonstration of lithographically etched silica-on-silicon monolithic integrated waveguide structures for single photon-pair experiments including high visibility non-classical interference and high fidelity implementation of a linear optical C-NOT quantum logic gate [1]. The integrated nature of these devices allows experiments to be reliably and stably realized on sophisticated photonic quantum circuits that would otherwise be inherently difficult to implement in bulk optics. We report the next step for silica photonic circuits by demonstrating stable and accurate control of single qubits and maximally entangled fock states. These results have direct application in quantum metrology [2], as well as more generally to fundamental quantum optics and optical quantum information processing [3]. Waveguide circuits can also be directly written into materials such as fused silica using tightly-focused femto-second lasers [4]; this technique has since been used to inscribe integrated devices such as monolithic waveguide-DFB-lasers [5]. We report here our progress on applying this technology to experiments in quantum optics. [1] A Politi, M Cryan, J G Rarity, S Yu, J L O'Brien, Science 320, 646 (2008) [2] T Nagata, R Okamoto, J L O'Brien, K Sasaki, S Takeuchi, Science 316, 726 (2007) [3] J L O'Brien, Science 318 1567 (2007) [4] K. M. Davis, K. Miura, N. Sugimoto, K. Hirao, Optic Lett, 21, 21 (1996). [5] G. D. Marshall, P. Dekker, M. Ams, J. A. Piper, and M. J. Withford, Opt. Lett., 33, 33 (2008). (hide abstract) Abstract:In this talk I will give an introduction to cat states and coherent state quantum computing (CSQC) as well as briefly discuss how approximations to small-amplitude cat states (kitten states) can be realised using squeezed light. I will then present theoretical results of how well we could expect these approximate kitten states to work in proof-of-principle demonstrations of coherent state teleportation. (hide abstract) Abstract:I explore the representation of quantum computing in terms of unitary reflection groups (groups of unitary transformations that leave invariant a hyperplane of a vector space). The Clifford group Cn normalizes the n-qubit Pauli group Pn (tensor products of Pauli matrices up to a phase) within the unitary group. Clifford group appeared in the context of self-dual error-correcting codes (E Bannai 99, G Nebe 00), and it is well known that C1 and C2 are related to complex reflection groups of the Shephard-Todd sequence. In quantum computing, Gottesman 97 discovered that Cn may be generated using two single qubit gates (Hadamard and phase Pi/4 gates) and a two-qubit gate (Controlled Not gate). In this work [Unitary reflection groups for quantum fault tolerance. Michel Planat and Maurice Kibler. Preprint 0807.3650 [quantph]. ], one uses some cristallographic reflection groups over the real Euclidean space (Coxeter groups), as well as imprimitive complex reflection groups. Imprimitive groups are related to the automorphisms of mutually unbiased bases of Pn. Coxeter groups of type B3 and G2 control the automorphisms of P1, and Coxeter systems of type D5 and E6 appear in the topological component of C2 and C3. There is thus a link with the geometry of smooth cubic surfaces. Finally group C3 contain the symmetries of octonions through its unique subgroups of order 168, 6048 and 12096, that are isomorphic to Lie groups PSL(2,7), SU(3,3) and G2(2). (hide abstract) Abstract:Optical quantum computation has represented one of the most successful testbed systems for quantum information processing. Along with ion-traps and Nuclear Magnetic Resonance (NMR), experimentalists have demonstrated control of qubits, multi-qubit gates and small quantum algorithms. However, photonic based qubits suffer from a problematic lack of a large scale architecture for fault-tolerant computation which could conceivably be built in the near future. While optical systems are, in some regards, ideal for quantum computing due to their high mobility and low susceptibility to environmental decoherence, these same properties make the construction of compact, chip based architectures difficult. Here I discuss many of the important issues related to scalable fault-tolerant quantum computation and introduce a feasible architecture design for an optics based computer. We combine the recent development of topological cluster state computation with the photonic module, simple chip based devices which can be utilized to deterministically entangle photons. The integration of this operational unit with one of the most exciting computational models solves many of the existing problems with other optics based architectures and leads to a feasible large scale design which can continuously generate a 3D cluster state with a photonic module resource cost linear in the cross sectional size of the cluster. (hide abstract) Abstract:We investigate the decay of entanglement of generalized $N$-particle Greenberger-Horne-Zeilinger (GHZ) states interacting with independent reservoirs. Scaling laws for the decay of entanglement and for its finite-time extinction (sudden death) are derived for different types of reservoirs. The latter is found to increase with the number of particles. However, entanglement becomes arbitrarily small, and therefore useless as a resource, much before it completely disappears, around a time which is inversely proportional to the number of particles. We also explore analytically and numerically how this behavior extends to other (more general) families of states. Finally, we show that the decay of multi-particle GHZ states can generate bound entangled states. (hide abstract) Abstract:One of the great successes of the field of quantum computation is the efficient quantum algorithm for the abelian hidden subgroup problem. In this talk, I'll discuss a generalisation of this task: the shifted subset problem. The problem is to determine a subset S of some abelian group, given access to quantum states of the form |S+x>, for some unknown shift x. In particular, I'll give quantum algorithms to find Hamming spheres and other subsets of the boolean cube {0,1}^n. The algorithms have time complexity polynomial in n and give rise to exponential separations from classical computation. (hide abstract) Abstract:Given a universal gate set on two qubits, it is well known that applying random gates from the set to random pairs of qubits will eventually yield an approximately Haar-distributed unitary. However, this requires exponential time. We show that random circuits of only polynomial length will approximate the first and second moments of the Haar distribution, thus forming approximate 1- and 2-designs. Previous constructions required longer circuits and worked only for specific gate sets. As a corollary of our main result, we also improve previous bounds on the convergence rate of random walks on the Clifford group. (hide abstract) Abstract:As was leaked to the press a long time ago, I have shown that deciding Markovianity of a quantum channel is NP-hard. (The people responsible for this leak will shortly be shipped off to the darkest depths of Asia.) What has not yet been leaked is the details and proof of this result, which I will attempt to explain in this talk. A quantum channel is Markovian iff it is a member of a one-parameter completely positive semi-group, i.e. if it can be generated by a master equation. Why should you care about this seemingly esoteric problem in the theory of CP-maps? Because master equations are the (most general possible) dynamical equations of a quantum system; they describe the underlying physics that produces the evolution. Whereas quantum channels describe the (most complete possible) measurements of that evolution; they describe what we can actually observe in the laboratory. NP-hardness of the Markovianity problem implies that extracting the dynamical equations of a quantum system from any sequence of measurements would take longer than the lifetime of the universe for even moderately sized systems (assuming P /= NP). This is a profound limitation imposed by quantum mechanics itself, raising intriguing conceptual question about quantum mechanics and quantum experiments, and is in stark contrast to the analogous problem in classical physics (which is in P). (hide abstract) Abstract:The ability to manipulate individual quantum systems, using quantum measurement and control, promises to bring about a quantum information revolution, including computers that are faster than any conceivable conventional computer. A recent application of ideas from these disciplines is the first ever experiment achieving the Heisenberg limit in interferometry [Higgins et al., Nature 450, 393-6 (2007).] Interferometry is used ubiquitously, for example to measure the optical properties of a sample (e.g. its refractive index). The Heisenberg limit represents the most accurate possible measurement given a limited resource (e.g. the number of photon-passes through the sample). We demonstrated this using single-photon technology developed for quantum computing, implementing an algorithm inspired by quantum computer algorithms, and modified using measurement and control theory. (hide abstract) Abstract:The quantum state of a many-body system can serve as a resource for a method of quantum computing based solely on adaptive local measurements. We show that the usefulness of the thermal state of a specific spin-lattice model for measurement-based quantum computing exhibits a sharp transition between two distinct 'phases' -- one in which every state is a universal resource for quantum computation, and other in which any local measurement sequence can be simulated efficiently on a classical computer. Remarkably, this transition in computational power does not coincide with any conventional phase transition in the underlying model; in fact, we demonstrate that this model does not possess any phase transitions, classical or quantum. The methods used to obtain our central results will likely have other applications - in particular we have obtained a method for correcting global, correlated errors in cluster state preparation, while on the other hand our method for classically simulating thermal projected entangled pair states (PEPS) should be applicable to a broad class of systems. (hide abstract) Abstract:Computational mechanics is a mathematical framework for constructing a model of a physical process where the result is argued to be unique/physical/natural. We introduce the causal state equivalence class that is the basis for this physicality. Further, measures defined on this model will serve as well motivated complexity measures on the process. Quantum finite state machines are a natural model class for discussing similar issues in regard to systems with an underlying quantum dynamic. It is desired to understand the relationship between these models and computational mechanics - both by applying the known methods to the quantum processes, and by searching for a quantum analogue to the causal state. Finally, we wish to characterize the 'quantum effects' through information theory measures and show some suggestive results. (hide abstract) Abstract:In quantum information theory, one of the most interesting open problems is the additivity conjecture. It states that the minimum output entropy of a pair of quantum channels should be the sum of the individual minimum entropies. A related problem is to determine if the minimum output p-norm for a bipartite channel is multiplicative. These problems can be seen as instances of a more general task: Determine the set of convex trace functions that attain their output maximum on unentangled input states. I report on some results and open problems for this generalized additivity problem. For example, I show that every operator convex function is "additive" in this sense for the Werner-Holevo channel, and give some speculation why von Neumann entropy and the p-"norms" for 1/2 < p < 1 might have special properties. (hide abstract) Abstract:We present elementary mappings between classical lattice models and quantum circuits. These mappings provide a general framework to obtain efficiently simulable quantum gate sets from exactly solvable classical models. For example, we recover and generalize the simulability of Valiant's match-gates by invoking the solvability of the free-fermion eight-vertex model. Our mappings furthermore provide a systematic formalism to obtain simple quantum algorithms to approximate partition functions of lattice models in certain complex-parameter regimes. For example, we present an efficient quantum algorithm for the six-vertex model as well as a 2D Ising-type model. We finally show that simulating our quantum algorithms on a classical computer is as hard as simulating universal quantum computation (i.e. BQP-complete). (hide abstract) Abstract:The purpose of a model of computation is to abstract away any unnecessary details, in order to allow the mathematician/scientist to deal with important subject matter, unburdened. One lesson that quantum computation has taught us is that a detail we had previously thought unimportant --the nature of the underlying physical processes doing the computations-- is not only significant, but actually crucial in determining answers to many fundamental computational questions. As such, there has been a push to go back to our traditional, classical, computation models --e.g. Turing machines, finite and cellular automata-- and 'quantize' them. In this talk I will argue that this process is not always done properly. The reason being that our traditional models of computation are not actual physical theories; and quantizing anything but a physical theory can lead to nonsensical results. In my talk I will use the cellular automata model as the prime example of computational model quantizations. I will use this example to illustrate a quantization approach and practical advantages of quantizing models of computation using this approach. (hide abstract) Abstract:An important open problem in quantum information is determining fault tolerance thresholds for various quantum computation architectures - i.e. the amount of noise physical components can tolerate before they become incapable of efficiently simulating quantum computation. Much work has been done on constructing clever encoding mechanisms that allow the designers to prove lower bounds on these thresholds. However, relatively little work has been done on constructing upper bounds. I present some elementary extensions of previous work on this topic, which allow the construction of tighter upper bounds for architectures based on clifford operations plus other single qubit/unitary resources, in particular for `state injection' schemes. (hide abstract) Abstract:A set of mutually unbiased bases of a quantum Hilbert space corresponds to a set of measurements, such that if two of them are performed, the result of the first provides minimal information about the possible results of the second. Such measurements are the most efficient way of determining the state if many copies are available. In a space of dimension d, at most d + 1 mutually unbiased bases can exist, but this number is known to exist only if d is a power of a prime. In this talk I will review the theory and survey the available evidence about the existence of mutually unbiased bases in non-prime-power dimensions. (hide abstract) Abstract:The quantum capacity of a quantum channel is the minimum number of qubits which can be transmitted per use of the channel, with arbitrarily small error, in the limit of many uses. An easily computable formula for the capacity is only known for special classes of channels, while only upper and lower bounds are known in general. In this talk, I will prove that the quantum capacity is not additive by showing the existence of two channels, each of which has zero capacity, while the capacity of their tensor product is strictly positive. This is joint work with Graeme Smith (IBM Watson Laboratory). (hide abstract) Abstract:Measurement-based quantum computation has shown us that entangled states can in some sense be considered to have "computational power". In classical computer science, the notion of computational power has been successfully formalised in the field of computational complexity theory. In this talk, I will describe an approach to the classification of the computational power of families of entangled states in measurement-based quantum computation. This will lead naturally to the notion of measurement based "classical computation", in our analysis of which, familiar states and constructions will arise. In our analysis, we will draw on concepts and techniques from computational complexity theory and quantum foundations (such as non-signalling non-locality) and illustrate some unexpected connections between them. Joint work with Janet Anders (UCL) The talk will be accessible to all with a general background in quantum information - computer science jargon will be explained! Reference: J. Anders and D.E. Browne - Measurement-based classical computation - on the arXiv next week or soon afterwards... (hide abstract) Abstract:The Bell-Kochen-Specker theorem demonstrates that the predictions of quantum theory are inconsistent with a noncontextual hidden variable model. Significantly, the notion of noncontextuality appearing in this theorem is only well-defined for models of quantum theory (and then only for projective measurements and deterministic models). By contrast, the notion of locality has not been so restricted in its scope -- Bell's definition of a local hidden variable model applies to any theory that can be described operationally. In this talk, I present a novel definition of noncontextuality that applies to any operational theory, and recovers (modulo some improvements) the traditional notion in the quantum context. With this definition, one can derive "contextuality inequalities" for experimental statistics, constraints that are implied by the existence of a noncontextual hidden variable model of those statistics (and violated by quantum theory). In this way, one can determine whether contextuality-inequality-violating theories provide information-theoretic advantages over their noncontextual counterparts. I demonstrate that this is indeed the case by showing that contextuality powers a certain kind of multiplexing scheme (joint work with Ben Toner). Time permitting, I will discuss an experiment by the group of Geoff Pryde that confirms the existence of this advantage. (hide abstract) Abstract:In 1972 Lieb and Robinson proved a bound on the velocity of propagation of correlations through an interacting spin system. This bound, when phrased in slightly more modern terms, says that all information, both classical and quantum, is exponentially attenuated outside of a light cone with an effective speed of light determined by the lattice structure. In this talk I will discuss Lieb-Robinson type bounds for systems with static and dynamical disorder. It turns out that, when disorder is present, the Lieb-Robinson bound can be replaced by a stronger bound. The bounds that arise depend on the nature and strength of the disorder and at least three types of behaviour can be identified: information propagates either ballistically, diffusively, or is strongly localised. Implications for fault tolerance in quantum computers will be sketched. (hide abstract) Abstract:Quantum error-correction and fault-tolerant computation rely crucially on the statistical independence of the noise that affects qubits at different times and locations. Within an n-spin-boson model we have quantitatively investigated to which extend this assumption is fulfilled in typical physical settings. I will present some evidence that noise-correlations that are introduced by the exchange of bosons between spins can drastically reduce the performance of QEC. (hide abstract) Abstract:Indistinguishable single photons in pure quantum states are a cornerstone of theoretical quantum optics. However, experimentally, it is not trivial to prepare them. For example, spontaneous parametric downconversion (SPDC) is commonly used to create heralded single photons but generally emits photon pairs into multiple correlated spatio-temporal modes, which introduces frequency and time jitter. I will explain how by careful design of the spaceâtime modes available to the photons generated by SPDC in a nonlinear crystal, we have prepared nearly indistinguishable heralded photons with a purity of at least 95%, the highest yet reported. Since the technique also raises the photon generation rate and heralding efficiency, and since purity is the current limiting factor for logic gate fidelity, this source should be very useful for photonic quantum information processing. Moreover, the design principle behind it can be widely applied. I will report on our theoretical and experimental progress in extending it to photon generation via four-wave mixing in photonic crystal fibre. For reasons I will explain, these sources should also prove uniquely useful for generating squeezed light. As well as generating quantum light, we are also active in developing new ways to detect it. To accurately characterize or reconstruct a quantum state one must first have a detector that is also well characterized. I will describe the first experimental detector tomography and present the measured POVMs of a standard photon detector and our home built photon-number detector. The latter is revealed to be a better single-photon detector than the standard photon detector in some respects. (hide abstract) Abstract:Entanglement is central both to the foundations of quantum theory and, as a novel resource, to quantum information science. The theory of entanglement establishes basic laws, such as the non-increase of entanglement under local operations, that govern its manipulation and aims to draw from them formal analogies to thermodynamics and the second law. However, while in the second law the entropy uniquely determines whether a state is adiabatically accessible from another, the manipulation of entanglement under local operations exhibits a fundamental irreversibility which prevents the existence of such an order. In this talk it will be shown that a reversible theory of entanglement and a rigorous relationship with thermodynamics may be established when one considers all non-entangling transformations. The role of entropy and the second law is taken by the asymptotic relative entropy of entanglement and the basic law of entanglement. The usefulness of this new approach to general resource theories and to quantum information theory will be discussed. The talk is based on a joint work with Martin Plenio. (hide abstract) Abstract:This talk will present recent results in the classification of entanglement types for pure n-qubit states. We illustrate a method of analysis that uses the Lie algebra of the group of local unitary transformations. Stabilizer subalgebra dimension and isomorphism class are invariants that separate entanglement types. High stabilizer dimension is associated with states with interesting entanglement properties. (hide abstract) Abstract:We give a simple recipe for translating walks on Cayley graphs of a group G into a quantum operation on any irrep of G. Most properties of the classical walk carry over to the quantum operation: degree becomes the number of Kraus operators, the spectral gap becomes the gap of the quantum operation (viewed as a linear map on density matrices), and the quantum operation is efficient whenever the classical walk and the quantum Fourier transform on G are efficient. This means that using classical constant-degree constant-gap families of Cayley expander graphs on e.g. the symmetric group, we can construct efficient families of quantum expanders. (hide abstract) Abstract:As you've no doubt already heard, a small band of brothers headed up by Lieutenant Winter scored dramatic victories in the war on additivity at the end of last year. But so far, you've only heard incomplete, censored information disseminated by the press and propaganda units. For the first time in Bristol, I will be giving a detailed, in depth report straight from the battle-front. Two of the big additivity questions of quantum information - additivity of the classical channel capacity and additivity of the entanglement of formation - are equivalent to additivity of the minimum output von Neumann entropy. The most popular way to attack (or defend) additivity is to consider the minimum output entropy problem for the more general p-Renyi entropies, where we recover the key von Neumann case at p=1. I will explain how Lieutenant Winter mounted a daring campaign against p>2, which Captain Hayden quickly followed up with his own attack, turning this initial breach into an astounding victory over all p>1. Additivity managed to regroup and retrench around p=1, and threw off the final assault, and a stand-off ensued. Mustering fresh forces, including NCOs Leung, Harrow and Montanaro and Corporal Cubitt, Lieutenant Winter organized a fresh attack on additivity from a new direction, which met with initial success at p=0, though for now seems to have become bogged down in difficult terrain. (hide abstract) Abstract:As physicists, we have become accustomed to the idea that a theory's content is always most transparent when written in coordinate-free language. But sometimes the choice of a good coordinate system is very useful for settling deep conceptual issues. Think of how Eddington-Finkelstein coordinates settled the longstanding question of whether the event horizon of a Schwarzschild black hole corresponds to a real spacetime singularity or not. Similarly we believe for an information-oriented or Bayesian approach to quantum foundations: That one good coordinate system may (eventually!) be worth more than a hundred blue-in-the-face arguments. This talk will motivate and chronicle the search for one such class of coordinate systems---the so-called Symmetric Informationally Complete Measurements---which has caught the attention of a handful of us at PI, a handful of our visitors, and a handful of other colleagues around the world. (hide abstract) Abstract:We show how a simple fact of algebraic geometry translates into quantum information theory, determining when subspaces of multipartite Hilbert space are generically completely entangled. This in turn implies other generic results concerning the local distinguishability of random quantum states, the separability of random mixed states, the indistinguishability of random subspaces, and a mathematically interesting generalisation of Schmidt rank. Joint work with Andrew Scott. (hide abstract) Abstract:The fact that non-orthogonal states cannot be distinguished with certainty is well known in quantum information. It may then be surprising to learn that non-orthogonal measurement bases can be distinguished with certainty if entanglement is used. In this talk I will give details of the first experiment to realise this use of entanglement - an experiment that uses a pair of photons generated from a Spontaneous Parametric Down Conversion Source. (hide abstract) Abstract:Randomness is a crucial resource in cryptography. It has been suggested that "good" randomness could be generated in an "unconditionally secure" way using quantum devices, e.g., a beam splitter followed by two photodetectors (and commercial devices have actually been built). In this talk, however, I show that in a model where all quantum devices are (only slightly) untrusted, it is generally impossible to generate randomness that is useful for cryptographic applications. (hide abstract) Abstract:Expander graphs are combinatorial objects which play an important role in classical computer science. A graph is an expander if it is simultaneously sparse and highly connected. Expanders seem to capture essential properties of random graphs: they often come into play when one is concerned with a property which "typically" holds, but defies systematic understanding. Very recently there has been some interest in constructing quantum analogues of expander graphs. Using phase space methods, we present the perhaps simplest way to quantize the perhaps simplest classical expander: the one due to Margulis. The talk will be largely conceptual - focusing on the basic ideas behind expanders and quantum phase spaces. (hide abstract) Abstract:As shown by Mayers, and Lo and Chau, even in the quantum setting it is impossible to achieve bit commitment and oblivious transfer in an unconditionally secure way. Damgaard et al. (FOCS '05, CRYPTO '07) showed how to securely implement bit commitment and oblivious transfer in a weaker setting called the bounded-quantum-storage model, where the adversary is only allowed to store a limited number of qubits. However, their security definitions did only apply to the standalone setting, and it was not clear if their protocols could be composed. We first give a simple attack that shows that these protocols (without any refinements to the model) are not composable. Then, we present a new, simulation-based definition for security in the bounded-quantum-storage model, and show that this definition allows for sequential composition of protocols. Finally, we prove the security of the randomized oblivious transfer protocol in our refined model. Secure implementations of oblivious transfer and bit commitment then follow easily by a (classical) reduction to randomized oblivious transfer. This is joint work with Stephanie Wehner. (hide abstract) Abstract:I will talk about the entanglement properties of thermal equilibrium states of many-body systems, with focus on harmonic lattices and quantum fields. I show that entanglement exists on the macroscopic scale and how it can be detected using thermodynamic quantities such as energy and temperature. I establish the parameter regimes where entanglement is present and discuss their dependency on the system parameters. In the case of the Bosonic gas, I link the entanglement to the occurrence of Bose-Einstein condensation in three dimensions. Moreover, I discuss the similarities between previous order concepts and entanglement as a new order concept. Finally, I suggest an analogy between measurement-based quantum computing and the process of phase transition in the two-dimensional Ising model and speculate about the implications of the presented ideas. (hide abstract) Abstract:The state of a quantum many-body system can serve as a universal resource for measurement-based quantum computing (MBQC). Such states may be created dynamically using entangling gates, but an alternate and possibly less demanding approach might be to cool a suitably gapped spin lattice with appropriate interactions close to its ground state. However, it would be unfortunate if the universality of such a ground state for the purposes of MBQC was critically dependent on the exact details of the Hamiltonian. A stronger result would be if its universality was robust over a finite range of parameters describing the Hamiltonian, such as the presence of local field terms, and for a finite temperature range. Could it be possible that, beyond simply the existence of a universal resource state for MBQC, there was an entire _phase_ in which any ground or low-temperature thermal state was universal for a fixed MBQC scheme? Using the cluster model (with Hamiltonian given by the sum of the stabilizers) and a local field term on one- and two-dimensional lattices, we provide evidence to support this idea. Specifically, we show the existence of phase transitions in the ground state, with long-ranged correlation functions for performing quantum gates serving as the order parameters. (hide abstract) Abstract:The leading proposals for quantum computation, either in the circuit or measurement-based models, all require the "hard work" of generating entanglement to be done dynamically. I will discuss the possibility that many-body systems may have a ground state which has suitable entanglement for quantum computation already - so that preparing the system amounts to simply cooling it. (hide abstract) Abstract:Measurement underpins all quantitative science, and advances in precision measurement often lead to new physical understanding. When technical noise is stripped away, the ultimate limit to measurement precision is set by the Heisenberg uncertainty principle. We demonstrate the first experimental Heisenberg-limited scaling of the phase variance in optical phase measurements. Our algorithm replaces complicated entangled states - widely thought to be essential for Heisenberg scaling - with single photons, multiple passes through a phase shift, and adaptive measurement. We show that although a single-photon version of Kitaev's phase estimation algorithm has standard-quantum-limited variance, our generalized technique is within a small constant factor of the ultimate quantum limit. (hide abstract) Abstract:I will talk about the geometric phase in quantum mechanics and some recent extensions. For a non cyclic evolution the geometric phase is undefined if the initial and final states are orthogonal. Similarly, the off-diagonal geometric phase is undefined for cyclic evolutions. We define a new kind of geometric phase which is always well defined and can be measured interferometrically. These nodal free geometric phases can also be used to construct various types of quantum phase gates. (hide abstract) Abstract:Bell's original inequality was based on the assumption of perfect anti-correlations. Because these are unobtainable in practice, it is often thought that the inequality is inadequate for testing local hidden variables in actual experiments. We show that this is not the case. We describe how to use both Bell's original inequality and a similar inequality for experimental tests of local hidden variables, despite both being in principle valid only for perfect anti-correlations. The second inequality can be used to demonstrate violation of local realism in conditions where commonly used inequalities fail. We implement both schemes experimentally, finding significant violations of both inequalities using polarisation-entangled photons. (hide abstract) Abstract:I will give a short introduction to classical simulation of quantum computation. I will then explain the tensor contraction approach for simulating quantum circuits. I will show how the approximate quantum Fourier transform circuit can be efficiently simulated using tensor contraction. Finally I will discuss the possibility of simulating the circuit for modular exponentiation (the other main component in Shor's algorithm) and show that an efficient tensor contraction scheme simulating this circuit can also efficiently simulate Shor's algorithm. (hide abstract) Abstract:Last month the Monroe group published a report in Nature describing a successful entanglement generation experiment. The novelty of experiment was that the physical qubits, two trapped ions, were located over a metre apart -- the entanglement was accomplished purely through making measurements on emitted photons. Using measurements as the basic mechanism for entanglement generation is an attractive idea, especially in terms of scalability. However this first experimental demonstration also highlighted some of the difficulties, not least the inherently probabilistic nature of the approach (in fact that only four in a billion attempts at entanglement succeeded). I will try to make that case that the QIP paradigm of optical measurements on remote matter qubits, whether they are atoms, NV centres or quantum dots, is nevertheless an exciting one -- perhaps even the most promising route to a real device. (hide abstract) Abstract:I will speak about spatial entanglement in the BEC phase transition. I will quantify the amount of entanglement between two spatial modes around the transition temperature for condensation and prove that long-range order is necessary for the existence of two-mode entanglement. I will compare the results for entanglement and long-range order to experimental measurements of spatial coherence and close agreement is found. Multi-mode entanglement also can be considered and I will illustrate the suitable conditions for three-mode entanglement. (hide abstract) Abstract:How are computing, information creation, and dynamics related? A contemporary view of these three historical threads is that they are not so disparate. I will show that a synthesis leads to methods to analyze how quantum processes store and manipulate information---what we refer to as "intrinsic quantum computation". I will introduce ways to measure information storage in quantum dynamics, using a recently introduced computation-theoretic model that accounts for measurement effects. The first, the entropy rate, quantifies the amount of inherent randomness in a process. The second, the excess entropy, quantifies the shared information between a quantum process's past and its future. A few examples of physical systems show how information processing is embedded in even simple quantum systems' behavior. (hide abstract) Abstract:I will start with a brief introduction to the use of spin chains for quantum communications. Following this, I will describe some methods to perfect these communications using certain reasonbable strategies when one uses chains in their ferromagnetic ground state. I will then briefly point out the use of antiferromagnetic spin chains for the same purpose. Next, I will discuss the use of bosons hopping freely in a one dimensional lattice to generate entanglement between its ends. I will also describe the generation of entanglement from the ground state of a chain of qudits coupled by purely exchange interactions. (hide abstract) Abstract:In this talk I will discuss some ongoing work on the convergence properties of random quantum circuits. A random circuit can be used to generate an approximate t-design for any t. In this work, we ask how many steps of the random circuit are required to do this. I will show that O(n^2) steps suffice for an approximate 2-design and will discuss approaches to proving similar results for higher t. (hide abstract) Abstract:An ideal spin chain with nearest-neighbour couplings can be used to communicate quantum information with high fidelity, and can therefore be used as a quantum wire. Unfortunately, any real spin chain will inevitably have an element of randomness inherent in the system. As a result, the chain will be affected by Anderson localization, a well studied phenomenon in solid state physics. Whereas a perfect lattice has energy eigenstates which extend throughout the system, randomness in the lattice Hamiltonian causes the energy eigenstates to become exponentially localized in space. This in turn inhibits state transfer and challenges the use of spin chains for quantum communication. In an attempt to mitigate the affects of localization in spin chains we shall consider sending the message states down multiple, parallel chains. By using quantum error correction at periodic intervals, we will find that it is possible to send a qubit over arbitrary distances, with arbitrarily good fidelity, using only a number of wires polylogarithmic in the distance propagated. (hide abstract) Abstract:I will summarise some recent work of mine on realistic quantum trajectories for a charge qubit. This realistic extension of quantum trajectory theory (continuous-in-time weak quantum measurement theory) accounts for experimental imperfections such as finite bandwidth and Johnson-Nyquist noise. It uses a more realistic signal to infer the qubit state as a function of time. If there is time, I will also present a very brief overview of my current research involving probing/characterising an environment of spins using single-qubit and double-qubit (entangled) probes. (hide abstract) Abstract:Single photon states (and other non-Gaussian states) are typically studied in the time domain. In contrast, continuous variable Gaussian states such as squeezed states are typically studied at side-band frequencies. Much of modern optical communcation technology is also based on side-band techniques. In this talk I will discuss what it means to produce single photon states at side-band frequencies and propose several techniques for producing, analysing and using such states. (hide abstract) Abstract:The standard oracle operator corresponding to a function f is a unitary operator that computes this function coherently, i.e. it maintains superpositions. This operator acts on a bipartite system, where the subsystems are the input and output registers. In distributed quantum computation, these subsystems may be spatially separated, in which case we will be interested in its classical and entangling capacities. For an arbitrary function f, we show that the unidirectional classical and entangling capacities of this operator are log_2(n_f) bits/ebits, where n_f is the number of different values this function can take. An optimal procedure for bidirectional classical communication with a standard oracle operator corresponding to a permutation on Z_M is given. The bidirectional classical capacity of such an operator is found to be 2 log_2(M) bits. The proofs of these capacities are facilitated by an optimal distributed protocol for the implementation of an arbitrary standard oracle operator. (hide abstract) Abstract:The elements of a unitary braid group representation (uBR) can be considered as quantum operations. Some of these representations establish new methods for fault tolerant quantum computing and quantum algorithms. However, we focus on uBRs of Yang-Baxter type and consider associated quantum circuits. In that case one can translate braids into quantum circuits simply by replacing braid strands by quantum wires and braid crossings by a fixed quantum gate R acting on appropriate quantum systems. After exploring some representation classes, we show how to efficiently simulate quantum circuits arising from certain representations. For qubits we conclude that all uBRs of Yang-Baxter type can be simulated efficiently. (hide abstract) Abstract:We study two qubit entanglement in the most general XYZ Heisenberg magnetic chain with (non)homogeneous magnetic fields and the DM anisotropic antisymmetric exchange interaction, arising from the spin-orbit coupling . The model includes all known results as particular cases, for both antiferromagnetic and ferromagnetic XX, XY, XXX, XXZ, XYZ chains. The concurrence of two qubit thermal entanglement and its dependence on anisotropic parameters, external magnetic field and temperature are studied in details. We found that in all cases, inclusion of the DM interaction, which is responsible for weak ferromagnetism in mainly antiferromagnetic crystals and spin arrangement in low symmetry magnets, creates (when it does not exist) or strengthens (when it exists) entanglement in XYZ spin chain. This implies existence of a relation between arrangement of spins and entanglement, in which the DM coupling plays an essential role. It suggests also that anisotropic antisymmetric exchange interaction could be an efficient control parameter of entanglement in the general XYZ case. (hide abstract) Abstract:In the recent seminar by Arleta Szkola, a Chernoff bound for symmetric quantum hypothesis testing was presented for the single party case. If the states to be discriminated are bipartite and the parties limited to LOCC operations things get significantly more complicated. For a particular family of data hiding states, we give the Chernoff bound by showing the optimal discimination strategy for any number of copies. (hide abstract) Abstract:Searching and sorting used as a subroutine in many important algorithms. Quantum algorithm can find a target item in a database faster than any classical algorithm. One can trade accuracy for speed and find a part of the database (a block) containing the target item even faster, this is partial search. An example is the following: exact address of the target item is given by a sequence of many bits, but we need to know only some of them. More generally partial search considers the following problem: a database is separated into several blocks. We want to find a block with the target item, not the target item itself. I will explain a quantum partial search algorithm. It can be considered as a rotation in three dimensional real space. It is based on quant-ph/0504157, quant-ph/0503238, quant-ph/0503238, quant-ph/0608106, quant-ph/0609205 (hide abstract) Abstract:Quantum versions of random walks on the line and cycle show a quadratic improvement in their spreading rate and mixing times respectively. The addition of decoherence to the quantum walk produces a more uniform distribution on the line, and even faster mixing on the cycle by removing the need for time-averaging to obtain a uniform distribution. By calculating the entanglement between the coin and the position of the quantum walker, the optimal decoherence rates are found to be such that all the entanglement is just removed by the time the final measurement is made. This requires only O(log T) random bits for a quantum walk of T steps. (hide abstract) Abstract:We present a method for describing and characterizing the state of N experimentally indistinguishable particles, that is to say particles that cannot be individually addressed due to experimental limitations. The technique relies upon a correct treatment of the exchange symmetry of the state among experimentally accessible and experimentally inaccessible degrees of freedom. Our technique is of direct relevance to current experiments in quantum optics, and my aim is to make the mathematics involved less mysterious so that the physics might be better appreciated. (hide abstract) Abstract:One of the major challenges in the theory of quantum computation is to develop new quantum algorithms. Much of the work on this question has focused on the nonabelian hidden subgroup problem (HSP), attempting to extend Shor's solution of the abelian HSP, the backbone of his efficient quantum algorithm for factoring integers. Unfortunately, these efforts have met with only limited success. In this talk, I will describe an alternative way of generalizing the success of Shor's algorithm. Shor's algorithm can be used to find hidden linear structures, so a natural generalization is to find hidden structures of higher degree. I will describe several problems involving hidden nonlinear structures. Typically, such problems have exponential classical query complexity, but polynomial quantum query complexity. Furthermore, some such problems can be solved in polynomial time by a quantum computer. This is joint work with Leonard Schulman and Umesh Vazirani. (hide abstract) Abstract:In this talk, I will discuss the generalisation of quantum search of unstructured and totally ordered sets to search of partially ordered sets (posets). I'll show that quantum algorithms for this task can achieve at most a quadratic improvement in query complexity over classical algorithms, up to logarithmic factors; I'll also give quantum algorithms that almost achieve this optimal reduction in complexity. I'll explicitly describe a quantum algorithm for searching forest-like posets and an optimal O(m^(1/2))-query quantum algorithm for searching posets derived from m*m arrays sorted by rows and columns. This leads to an optimal O(n^(1/2))-query quantum algorithm for finding the intersection of two sorted lists of n integers. (hide abstract) |