The Ninth Workshop on
Quantum Information Processing
Paris, January 16-20, 2006

General information | Call for communications | Practical information
List of posters | List of talks | Abstracts | Schedule | Group photo | Other photos

Abstracts of talks

Invited talks

A new quantum lower bound method, with applications to strong direct product theorems
by Andris Ambainis (University of Waterloo), joint work with Robert Spalek, Ronald de Wolf

Quantum query model can be used to analyze many quantum algorithms, including Grover's search, quantum counting and others. Many of those algorithms can be shown to be optimal, by proving matching quantum lower bounds. So far, most of quantum lower bounds have been proven by two methods: polynomials method and adversary method. Both strengths and limitations of these two methods have been quite well understood.

We describe a new method for proving lower bounds on quantum algorithms in the query model. The new method builds on the adversary method, but avoids its limitations and can be used to prove bounds which are impossible to prove by the previous adversary method.

We apply the new method to two problems. The first one is k-fold search problem, in which we have k instances of Grover's search problem. In each instance, we have to find one marked element among n elements. The task is to solve them all simultaneously. The second problem is simultaneously computing t-threshold function on k inputs, each of which consists of N bits. We show that:

  1. any algorithm for the k-fold search problem that uses less than c ksqrt{N} queries can only succeed with an exponentially small probability;
  2. any algorithm for t-threshold functions that uses less than c k sqrt{N t} queries can only succeed on all k copies simultaneously with an exponentially small probability.

The first lower bound has been previously shown by Klauck, Spalek and de Wolf, using polynomials method. No lower bound using adversary method was known. The second bound is new. Both lower bounds have applications to proving time-space tradeoffs for quantum algorithms.

Quantum information with Rydberg atoms and photons in cavities: results and perspectives
by Serge Haroche (Collège de France and Ecole Normale Supérieure, Paris)
Fourier sampling, representations, and the hunt for a quantum algorithm for Graph Isomorphism
by Cris Moore (University of New Mexico), joint work with Alex Russell, Leonard Schulman

I give an introduction to Fourier sampling and representation theory. I then discuss recent results, both positive and negative, about the possibility of using Fourier sampling to solve Graph Isomorphism on a quantum computer.

Rigorous fault-tolerance thresholds
by Ben Reichardt (University of California, Berkeley)

Efficient fault-tolerance schemes have narrowed the gap between estimated noise threshold lower bounds and known upper bounds. (The noise threshold is the highest tolerable error rate.) Efficient proof techniques are allowing rigorous proofs of higher threshold lower bounds than before, although there is still a substantial gap between the proven and the estimated threshold rates. The new proof techniques apply to concatenated distance-three codes, for which there had been no proven positive threshold at all.

An exponential de Finetti theorem and its applications to quantum cryptography
by Renato Renner (CQC, Cambridge)

The state of an n-partite product system is said to be symmetric if it is invariant under permutations of the n subsystems. We show that any symmetric state is exponentially (in n) close to a mixture of "almost product" states, i.e., states which have product form except on a small number of subsystems. Most of the relevant properties of such "almost product" states are virtually equal to those of perfect product states.

The result has applications in quantum information theory. It implies, for example, that in order to prove full security of a QKD protocol it suffices to consider so-called collective attacks, where the adversary is bound to apply identical and independent operations on each of the particles sent over the quantum channel.

Cryptography in the Bounded Quantum-Storage Model
by Christian Schaffner (BRICS, University of Aarhus), joint work with Ivan B. Damgaard, Serge Fehr, Louis Salvail

We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's quantum memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least n/2 in order to break the protocol, where n is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient, non-interactive and can be implemented using today's technology. On the technical side, a new uncertainty relation is established.

This is joint work with Ivan B. Damgård, Serge Fehr and Louis Salvail

Graph Isomorphism, the hidden subgroup problem and distinguishing quantum states
by Pranab Sen (NEC Labs America), joint work with Sean Hallgren, Martin Rotteler

It has been known for some time that graph isomorphism reduces to the hidden subgroup problem (HSP) in the symmetric group. The standard quantum approach for the HSP involves identifying the hidden subgroup from its coset state, namely, from the uniform mixture of uniform superpositions over cosets of the hidden subgroup. It was recently shown by Moore, Russell and Schulman that exponentially many measurements are required to determine whether two graphs are isomorphic or not if each measurement is limited to act on one or two coset states at a time. We show that any efficient quantum algorithm for graph isomorphism operating only on coset states needs to make measurements entangled across Omega(n log n) states, matching an old information theoretic upper bound of Ettinger, Høyer and Knill. This may be viewed as a negative result because highly entangled measurements seem hard to implement in general. Our main theorem is quite general and also rules out using joint measurements on few coset states for the HSP in some other groups.

Next, we show that for any two quantum states in n-dimensional space, with high probability a random POVM, for a suitable notion of randomness, gives total variation distance at least a universal constant times their Frobenius distance divided by log n. Applied to the HSP, this result shows that polynomially many iterations of random Fourier sampling on one coset state at a time suffice to information theoretically identify hidden subgroups that have polynomially bounded rank in every representation of the ambient group. In particular, this is the case for Gel'fand pairs, for example dihedral and Heisenberg groups, where the rank is zero or one for every representation. This result provides a positive counterpart to the above lower bound for HSP in the symmetric group, where the rank of the hidden subgroup in most representations is exponentially large.

Zero-knowledge against quantum attacks
by John Watrous (University of Calgary)

It has been an unsolved problem in theoretical quantum cryptography for several years to formulate a general and cryptographically meaningful definition of quantum zero-knowledge and to apply the definition to non-trivial protocols. In this talk I will explain how this problem can be solved, at least to a significant extent, for what are arguably the strongest and most natural definitions of quantum zero-knowledge.

Long talks

Verifiable Quantum Secret Sharing and Secure Multi-Party Quantum Computation
by Michael Ben-Or (Hebrew University), joint work with Claude Crépeau, Daniel Gottesman, Avinatan Hassidim, Adam Smith

Classical and quantum strategies for two-prover bit commitments
by Claude Crépeau (McGill University), joint work with Jean-Raymond Simard, Alain Tapp
From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
by Wim van Dam (University of California, Santa Barbara), joint work with Andrew M. Childs, Dave Bacon

We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form (Z_p)^r X| Z_p for fixed r (including the Heisenberg group, r=2). In particular, our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP.
Ref.: arXiv:quant-ph/0504083

Bounded-Error Quantum State Identification with Applications to Communication Complexity
by Dmitry Gavinsky (University of Calgary), joint work with Julia Kempe, Oded Regev, Ronald de Wolf

We consider the problem of bounded-error quantum state identification: given one of two known states, what is the optimal probability a with which we can identify the given state, subject to our guess being correct with high probability (but we are permitted to output "don't know" instead of a guess). We prove a direct product theorem for this problem. Our proof is based on semidefinite programming duality and may be of wider interest.

Using this result, we present two new exponential separations in the simultaneous message passing model of communication complexity. Both are shown in the strongest possible sense:

A different kind of quantum search
by Lov Grover (Bell Labs, Lucent)

Quantum searching normally consists of an alternate sequence of selective inversion and diffusion operations. The algorithm has been extensively studied and is well understood. However, there was a surprising result that was discovered last year.

This showed that if we replace the selective inversions by Pi/3 phase shifts the algorithm behaves something like a classical algorithm that is easier to describe in terms of probabilities. Several new results follow from this. For example, we obtain an algorithm that converges monotonically towards the solution [1]. This is in contrast to the well-known search/amplitude amplification algorithms that have an oscillatory character.

If we consider a situation where the probability of getting a target state for a random item, is 1-epsilon (with epsilon unknown), then the probability of getting a target state after a single query in the new algorithm, can be increased to 1-epsilon3, classically this can be increased to only 1-epsilon2. The performance of this algorithm has recently been proved to be optimal. Another important application of this technique is in correction of systematic errors [2].

(1) L.K. Grover (2005), Fixed-point quantum search, Phys. Rev. Letters, Oct. 3, 2005.
(2) B.W. Reichardt and L.K. Grover, Quantum error correction of systematic errors using a quantum search framework, Phys. Rev. A, Oct. 25, 2005

The classical and quantum private capacities of a secret shared Cartesian frame
by Patrick Hayden (McGill University), joint work with Stephen Bartlett, Robert Spekkens

A private shared Cartesian frame is a novel form of private shared correlation that allows for both private classical and quantum communication. Cryptography using a private shared Cartesian frame has the remarkable property that asymptotically, if perfect privacy is demanded, the private classical capacity is three times the private quantum capacity. I'll explain how, if the requirement for perfect privacy is relaxed, it is possible to use the properties of random subspaces to nearly triple the private quantum capacity, almost closing the gap between the private classical and quantum capacities.

Quantum Network Coding
by Kazuo Iwama (Kyoto University), joint work with Masahito Hayashi, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita

Since quantum information is continuous, its handling is sometimes surprisingly harder than the classical counterpart. A typical example is cloning; making a copy of digital information is straightforward but it is not possible exactly for quantum information. The question in this talk is whether or not "quantum" network coding is possible. Its classical counterpart is another good example to show that digital information flow can be done much more efficiently than conventional (say, liquid) flow.

Our answer to the question is similar to the case of cloning, namely, it is shown that quantum network coding is possible if approximation is allowed, by using a simple network model called Butterfly. In this network, there are two flow paths, s_1 to t_1 and s_2 to t_2, which shares a single bottleneck channel of capacity one. In the classical case, we can send two bits simultaneously, one for each path, in spite of the bottleneck. Our results for quantum network coding include: (i) We can send any quantum state |psi_1> from s_1 to t_1 and |psi_2> from s_2 to t_2 simultaneously with a fidelity strictly greater than 1/2. (ii) If one of |psi_1> and |psi_2> is classical, then the fidelity can be improved to 2/3. (iii) Similar improvement is also possible if |psi_1> and |psi_2> are restricted to only a finite number of (previously known) states. This allows us to design an interesting protocol which can send two classical bits from s_1 to t_1 (similarly from s_2 to t_2) but only one of them should be recovered.

A de Finetti theorem for finite quantum states - Locked correlations and secret keys
by Robert Koenig (CQC, Cambridge), joint work with Renato Renner

Consider a state on an n-fold product space which is invariant under permutations of the subsystems. We show that applying an informationally complete POVM to a number of subsystems gives a residual state which is close to having product form. We briefly point out some implications of the resulting so-called de Finetti representation.

In the second part of this talk, we show that security definitions in quantum key distribution based on the accessible information are generally insufficient to guarantee security in applications. This is due to the existence of locked classical correlations. We also discuss how to overcome this problem.

A classical analog of negative information
by Jonathan Oppenheim (University of Cambridge), joint work with Rob Spekkens, Andreas Winter

'Quantum partial information' is the amount of communication needed for one party to send her share of a state to a receiver who holds part of the state. Recently, it was shown that it is given by the conditional entropy, which can be negative. If, in addition one also requires that the receiver send his state to the sender (quantum state exchange), the amount of information which needs to be sent can paradoxically go down. Here we find a classical analogue of these results, based on a long known relationship between entanglement and shared private correlations: namely, we consider a private distribution held between two parties, and correlated to a reference system, and ask how much secret communication is needed for one party to send her distribution to the other. We give optimal protocols for this task, and find that private information can be negative - the sender's distribution can be transferred and the potential to send future distributions in secret is gained through the distillation of a secret key. Exchanging a distribution can also cost less than for one party to send it. The results give new classical protocols, and also clarify the various relationships between entanglement and privacy.

A fault-tolerant one-way quantum computer
by Robert Raussendorf (Caltech), joint work with Jim Harrington, Kovid Goyal

We describe a fault-tolerant one-way quantum computer on cluster states in three dimensions. The presented scheme uses methods of topological error correction resulting from a link between cluster states and surface codes. The error threshold is 1.4% for local depolarizing error and 0.11% for each source in an error model with preparation-, gate-, storage- and measurement errors.

Simulating quantum computation by contracting tensor networks
by Yaoyun Shi (University of Michigan, Ann Arbor), joint work with Igor Markov

Are quantum computers truly more powerful than classical ones, or any quantum computation can be simulated efficiently classically? While most of us believe the former, the possibility for the latter is not yet ruled out in theory. In this talk, I will present a general classical algorithm for simulating quantum computation.

The treewidth of a graph is a useful combinatorial measure on how close the graph is to a tree. We prove that a quantum circuit with T gates whose underlying graph has treewidth d can be simulated classically in TO(1)*exp(O(d)) time, which, in particular, is polynomial in T if d = O(logT). To our knowledge, this work makes the first connection of treewidth and quantum computation, and some of our simulation results appear difficult to obtain using previous methods.

Communicating over adversarial quantum channels
by Graeme Smith (Caltech), joint work with Aram Harrow, Debbie Leung
Irreversibility for all bound entangled states
by Barbara Synak-Radtke (University of Gdansk), joint work with Dong Yang, Michal Horodecki, Ryszard Horodecki

We derive a new inequality for entanglement for a mixed four-partite state. Employing this inequality, we present a one-shot lower bound for entanglement cost and prove that entanglement cost is strictly larger than zero for any entangled state. We demonstrate that irreversibility occurs in the process of formation for all non-distillable entangled states. In this way we solve a long standing problem, of how "real" is entanglement of bound entangled states. Using the new inequality we also prove impossibility of local-cloning of a known entangled state. The result, that we obtain also implies that the mathematical definition of entangled states is equivalent to the physical definition in the sense of states preparation by LOCC.

New Limits on Fault-Tolerant Quantum Computation
by Falk Unger (CWI), joint work with Harry Buhrman, Richard Cleve, Monique Laurant, Noah Linden, Alexander Schrijver

We show that quantum circuits cannot be made fault-tolerant against a depolarizing noise level of theta =45%, thereby improving on a previous bound of 50% (due to Razborov). Our precise quantum circuit model enables perfect gates from the Clifford group and arbitrary additional one-qubit gates that are subject to depolarizing noise theta. We prove that this set of gates cannot be universal for arbitrary (even classical) computation, from which the upper bound on the noise threshold for fault-tolerant quantum computation follows.

On the complexity of simulating quantum systems
by Frank Verstraete (Caltech)
Extremality of Gaussian quantum states
by Michael Wolf (Max Planck Institut für Quantenoptik, Garching), joint work with Geza Giedke, Ignacio Cirac

We investigate Gaussian quantum states in view of their exceptional role within the space of all continuous variables states. A general method for deriving extremality results is provided and applied to entanglement measures, secret key distillation and the classical capacity of Bosonic quantum channels. We prove that for every given covariance matrix the distillable secret key rate and the entanglement, if measured appropriately, are minimized by Gaussian states. This result leads to a clearer picture of the validity of frequently made Gaussian approximations. Moreover, it implies that Gaussian encodings are optimal for the transmission of classical information through Bosonic channels, if the capacity is additive.

Short talks

Quantum entanglement can be simulated without communication
by Nicolas Cerf (Université Libre de Bruxelles), joint work with Nicolas Gisin, Serge Massar, Sandu Popescu
Simulating quantum correlations as a distributed sampling problem
by Julien Degorre (Université Paris-Sud, Orsay), joint work with Sophie Laplante, Jérémie Roland

It is known that quantum correlations exhibited by a maximally entangled qubit pair can be simulated with the help of shared randomness, supplemented with additional resources, such as communication, postselection or nonlocal boxes. For instance, in the case of projective measurements, it is possible to solve this problem with protocols using one bit of communication or making one use of a nonlocal box. We show that this problem reduces to a distributed sampling problem. We give a new method to obtain samples from a biased distribution, starting with shared random variables following a uniform distribution, and use it to build distributed sampling protocols. This approach allows us to derive, in a simpler and unified way, many existing protocols for projective measurements, and extend them to positive operator value measurements. Moreover, this approach naturally leads to a local hidden variable model for Werner states.

Dualities in quantum information theory
by Igor Devetak (University of Southern California)
Quantum computation as geometry
by Andrew Doherty (University of Queensland), joint work with Michael Nielsen, Mark Dowling, Mile Gu
From Bell's Theorem to Secure Quantum Key Distribution
by Nicolas Gisin (Geneva University), joint work with Antonio Acin, LLuis Masanes
Asymmetric unitary gate capacities
by Aram Harrow (University of Bristol), joint work with Peter Shor
Quantum Search in an Ordered List via Adaptive Learning
by Avinatan Hassidim (The Hebrew University), joint work with Michael Ben-Or

We improve the results of Farhi et al. cite{FGGS99} and present a quantum search algorithm in an ordered list of complexity less than log2(n)/3. To do so, we study and analyze some classical noisy search problems which are of independent interest.

Farhi et al presented in cite{FGGS99} two quantum algorithms for searching an ordered list. They first presented a ``greedy'' algorithm with small error probability that clearly outperformed classical algorithms. The other algorithm was based on the fact that with just three quantum queries one can find the correct element in a sorted list of length 52. Iterating this as a subroutine gives an 0.5log2(n) quantum search algorithm. This was recently improved by Jacokes, Landahl and Brooks, using 4 queries on 434 long lists, giving a quantum search algorithm using 0.457log2(n) queries cite{JLB05}. While the asymptotic complexity of the greedy algorithm remains an intriguing open problem we use it, when applied to constant size arrays, to obtain a faster quantum search algorithm. Since the greedy algorithm has a non zero error probability we must develop highly efficient classical noisy search algorithm to obtain our result.

Unconditionally secure privacy using channels that cannot convey quantum information
by Karol Horodecki (University of Gdansk), joint work with M. Horodecki, P. Horodecki, D. Leung, H-K. Lo, J. Oppenheim

Recently, it was shown that one can obtain perfectly secure corellations after one performs a measurement on a bound-entangled state. One also can recast cryptography into a theory which looks similar to entanglement distillation with maximally entangled states replaced with "private states". Here, we present the result, that one can extend this to a more traditional scenario where an adversary gives two parties such bound entangled states states and they have to verify privacy. This implies that, somewhat surprisingly, prefect and unconditional security can be obtain with channels that are unable to transmit feithfully any quantum information.

Schumacher compression with minimum time-space product
by Masahiro Kitagawa (Osaka University / JST)

We have reduced the auxiliary workspace of Schumacher compression for n-qubit sequence to O(log n) and the time-space product to O((n log n)^2), which is the known minimum for efficient algorithms that asymptotically approach the von Neumann limit.

Quantum communication by erasure channel assisted by back classical communication
by Debbie Leung (University of Waterloo), joint work with Peter Shor
A limit on nonlocality in any world in which communication complexity is not trivial
by André Méthot (Université de Montréal), joint work with Gilles Brassard, Harry Buhrman, Noah Linden, Alain Tapp, Falk Unger

Bell proved that quantum entanglement enables two space-like separated parties to exhibit classically impossible correlations. Even though these correlations are stronger than anything classically achievable, they cannot be harnessed to make instantaneous (faster than light) communication possible. Yet, Popescu and Rohrlich have shown that even stronger correlations can be defined, under which instantaneous communication remains impossible. This raises the question: Why are the correlations achievable by quantum mechanics not maximal among those that preserve causality? We give a partial answer to this question by showing that slightly stronger correlations would result in a world in which communication complexity becomes trivial.

Self-Testing of Quantum Circuits
by Harold Ollivier (Perimeter Institute), joint work with Frédéric Magniez, Dominic Mayers, Michele Mosca

We prove that a quantum circuit together with measurement apparatuses and EPR sources can be fully verified without any reference to some other trusted set of quantum devices. Our main assumption is that the physical system we are working with consists of several identifiable sub-systems, on which we can apply some given gates locally. To achieve our goal we define the notions of simulation and equivalence. The concept of simulation refers to producing the correct probabilities when measuring physical systems. To enable the efficient testing of the composition of quantum operations, we introduce the notion of equivalence. Unlike simulation, which refers to measured quantities (i.e., probabilities of outcomes), equivalence relates mathematical objects like states, subspaces or gates.

Using these two concepts, we prove that if a system satisfies some simulation conditions, then it is equivalent to the one it is purposed to implement. In addition, with our formalism, we can show that these statements are robust, and the degree of robustness can be made explicit (unlike the robustness results of [DMMS00]). In particular, we also prove the robustness of the EPR Test [MY98]. Finally, we design a test for any quantum circuit whose complexity is linear in the number of gates and qubits, and polynomial in the required precision.

The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
by Tobias Osborne (Royal Holloway, University of London)

In this talk I'll provide an improved short proof that an arbitrarily good approximation to the propagator e^{itH} for a 1D lattice of n quantum spins with hamiltonian H may be obtained with polynomial computational resources in n and the error epsilon, and exponential resources in |t|. There are two immediate consequences of this result. The first is that the Vidal's time-dependent density matrix renormalisation group requires only polynomial resources to simulate 1D quantum spin systems for logarithmic |t|. The second consequence is that continuous-time 1D quantum circuits with logarithmic |t| can be simulated efficiently on a classical computer, despite the fact that, after discretisation, such circuits are of polynomial depth. The new proof does not make use of the matrix product state/finitely correlated state formalism. Rather, the calculations are carried out in the Heisenberg picture. Extensions to higher dimensions and to simulating adiabatic quantum algorithms in 2D will be outlined.

Monogamy of nonlocal quantum correlations
by Benjamin Toner (Caltech)

We describe a new technique for obtaining Tsirelson bounds, or upper bounds on the quantum value of a Bell inequality. Since quantum correlations do not allow signaling, we obtain a Tsirelson bound by maximizing over all no-signaling probability distributions. This maximization can be cast as a linear program. In a setting where three parties, A, B, and C, share an entangled quantum state of arbitrary dimension, we: (i) bound the trade-off between AB's and AC's violation of the CHSH inequality, and (ii) demonstrate that forcing B and C to be classically correlated prevents A and B from violating certain Bell inequalities, relevant for interactive proof systems and cryptography.

Entanglement in Interactive Proof Systems with Binary Answers
by Stephanie Wehner (CWI)

If two classical provers share an entangled state, the resulting interactive proof system is significantly weakened [quant-ph/0404076]. We show that for the case where the verifier computes the XOR of two binary answers, the resulting proof system is in fact no more powerful than a system based on a single quantum prover: +MIP*[2] is contained in QIP(2). This also implies that +MIP*[2] is contained in EXP which was previously shown using a different method [Presentation of Cleve et al. at CCC'04]. This contrasts with an interactive proof system where the two provers do not share entanglement. In that case, +MIP[2] = NEXP for certain soundness and completeness parameters [quant-ph/0404076].

Lower Bounds on Matrix Rigidity via a Quantum Argument
by Ronald de Wolf (CWI)

The rigidity of a matrix measures how many of its entries need to be changed in order to reduce its rank to some value. Good lower bounds on the rigidity of an explicit matrix would imply good lower bounds for arithmetic circuits as well as for communication complexity. Here we reprove the best known bounds on the rigidity of Hadamard matrices, due to Kashin and Razborov, using tools from quantum computing.Our proofs are somewhat simpler than earlier ones (at least for those familiar with quantum) and give slightly better constants. More importantly, they give a new approach to attack this longstanding open problem.