34
talks
0
posters
10
regular papers
24
invited talks
0
awards
34
unique authors
27
committee members
Programme
| Title | Type | Date | Min | Authors | Award |
|---|---|---|---|---|---|
| A new generic proof for the security of quantum key distribution | regular | — | 15 | Matthias Christandl | — |
| Holographic Algorithms | invited | — | 50 | Leslie Valiant | — |
| Quantum Foundations in the Light of Quantum Information | invited | — | 50 | Gilles Brassard | — |
| Quantum walk algorithms: element distinctness and spatial search | invited | — | 50 | Andris Ambainis | — |
| Sharing secret quantum states: theory and experiment | regular | — | 15 | Barry Sanders | — |
| Coherent communication of classical messages | regular | — | 15 | Aram Harrow | — |
| Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect | regular | — | 15 | David Poulin | — |
| Multilinear Formulas and Skepticism of Quantum Computing. | invited | — | 50 | Scott Aaronson | — |
| Non locality | invited | — | 50 | Serge Massar | — |
| Quantum Algorithms for the Triangle Problem We present two new quantum algorithms that either finds a triangle in an undirected graph G on n nodes, or rejects if G is triangle free. The first algorithm uses combinatorial ideas with Grover Search and makes \tilde{O}(n^{10/7}) queries. The second algorithm uses O(n^{13/10}) queries, and it is based on a new design concept of Ambainis that incorporates the benefits of quantum walks into Grover search. The first algorithm uses only O(log n) qubits in its quantum subroutines, whereas the second one uses O(n) qubits. Note: joint work with Miklos Santha and Mario Szegedy Serge Massar: Non locality We describe the geometry of the space of non local correlations and we show how it is possible to interconvert between different types of non local correlations. This should form the basis for developping an information theory of non local correlations. Ueli Maurer: On the Power of Quantum Memory A qubit can be used to implement a classical memory bit, but not vice versa. We address the question whether quantum memory can be more powerful than classical memory in a classical information context where some relevant information X (e.g. an n-bit string) must be stored in memory of insufficient size s (e.g. s We discuss an information-theoretic model of memory, which includes quantum memory, and show that in a quite general context, quantum memory is only marginally more powerful than classical memory. In particular, classical privacy amplification by universal hashing remains secure even against an adversary with (the same amount of) quantum rather than classical memory. It remains a general open problem to prove certain classical information-theoretic cryptosystems, for instance schemes secure in the bounded-storage model, secure in presence of a quantum adversary. This is joint work with Robert Koenig and Renato Renner. Jaikumar Radhakrishnan: The bounded-round quantum communication complexity of set disjointness In the set disjointness problem, there are two parties A and B, each with a subset of {1,...,n}. They wish to communicate to determine if their sets are disjoint. For this problem quantum protocols do provably better than classical protocols. Recently, Aaronson and Ambainis showed a protocol for this problem where the two parties exchange O(sqrt{n}) qubits, matching the previous lower bound of Omega(sqrt{n}) shown by Razborov. (The classical randomized communication complexity of this problem is theta(n).) We consider bounded-round quantum communication protocols for the set disjointness problem, and show that in any communication protocol with k rounds, the two parties must exchange Omega(n/k^2) qubits. This lower bound is obtained by adapting the the information theoretic proof technique of Bar-Yossef, Jayram, Kumar and Sivakumar to the quantum setting. An upper bound of O(n/k) follows easily from the O(sqrt{n}) upper bound due to Aaronson and Ambainis. For protocols with no restriction on the number of rounds, we can conclude that the two parties must exchange Omega(n^{1/3}) qubits. This, however, falls short of the optimal Omega(sqrt{n}) lower bound shown by Razborov. Ran Raz: Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size I will talk about recent lower bounds for multi-linear arithmetic formulas. A surprising and beautiful application of these bounds in the field of quantum computation was recently found by Scott Aaronson [Scott Aaronson, "Multilinear Formulas and Skepticism of Quantum Computing"], and will be discussed in his talk. In my talk, I plan to give a short introduction to the problem as well as the main ideas of the lower bounds proof. Some more details are given below: Arithmetic formulas for computing the determinant and the permanent of a matrix have been studied since the 19th century. Are there polynomial size formulas for these functions? Although the determinant and the permanent are among the most extensively studied computational problems, polynomial size formulas for these functions are not known. An outstanding open problem in complexity theory is to prove that polynomial size formulas for these functions do not exist. Note, however, that super-polynomial lower bounds for the size of arithmetic formulas are not known for any explicit function and that questions of this type are considered to be among the most challenging open problems in theoretical computer science. An arithmetic formula is multi-linear if the polynomial computed by each of its sub-formulas is multi-linear, that is, in each of its monomials the power of every input variable is at most one. Multi-linear formulas are restricted, as they do not allow the intermediate use of higher powers of variables in order to finally compute a certain multi-linear function. Note, however, that for many multi-linear functions, formulas that are not multi-linear are very counter-intuitive. Note also that both the determinant and the permanent are multi-linear functions and that many of the well known formulas for these functions are multi-linear formulas. We prove that any multi-linear arithmetic formula for the determinant or the permanent of an n dimensional matrix is of size super-polynomial in n. Previously, no lower bound was known (for any explicit function) even for the special case of multi-linear formulas of constant depth. Oded Regev: Recent connections between quantum computation and lattice problems I will describe a result obtained together with Dorit Aharonov on lattice problems in quantum NP and a more recent result showing how to dequantize the construction in order to obtain containment in NP. Time permitting, I will also comment on the possibility of applying Kuperberg's algorithm to solve lattice problems in subexponential time. Alex Russell: Quantum Computation in Groups This talk will survey some recent developments in the theory of quantum computation in groups, focusing on two primary research efforts: development of efficient quantum Fourier transforms and development of efficient solutions to hidden subgroup problems. Quantum Fourier transforms. The talk will describe a "quantization" of the successful separation of variables technique, the generic framework responsible for most known efficient classical Fourier transform algorithms. This results in a wide family of efficient quantum circuits for the quantum Fourier transform, recovering all known efficient quantum Fourier transforms and providing efficient transforms for many new groups. In addition, it gives the first subexponential quantum circuits for the Fourier transform over several interesting linear groups. Hidden subgroup problems. The talk will discuss some recent advances in our understand of the hidden subgroup problems, discussing new closure properties and solutions for families of groups which appear to require the strong standard method. Leonard Schulman Physical limits of heat-bath algorithmic cooling Peter Shor: Additivity questions in quantum information theory There are a number of interesting, open additivity questions in quantum information theory. Recently, I have been able to show that some of these are equivalent. I will discuss open additivity questions in general and this proof of equivalence in particular. Kiyoshi Tamaki: Unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel We prove the unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel. We assume that Alice has an ideal single photon source and Bob has detectors that discriminate between single photon states on one hand and vacuum state or multiphoton states on the other hand. We use a reduction to an entanglement distillation protocol initiated by a local filtering process in our proof. The bit errors and the phase errors are correlated after the filtering, and we can bound the amount of phase errors from the observed bit errors by an estimation method involving nonorthogonal measurements. Leslie Valiant: Holographic Algorithms John Watrous: Stronger Error Reduction for QMA The complexity class QMA is a bounded-error quantum computational variant of the class NP, where a quantum state plays the role of a certificate. It is known that the error of a given QMA protocol can be reduced exponentially at the cost of a polynomial increase in the length of the certificate. In this talk, I will prove that such a reduction in error is in fact possible with no increase in the length of the certificate whatsoever. Applications of this fact include a proof that logarithmic-length quantum certificates give no increase in power over BQP and a simple proof that QMA is contained in the class PP. Andreas Winter: From entanglement to secret key and back The last year has seen a series of dramatic progresses in the areas of quantum channel capacities, entanglement distillation and our understanding of how these problems relate to secret communication. In this talk I will first review the analogy between the theories of entanglement and key distillation. Then I go on to explain the elements of the recent progress, first describing Devetak's recent reduction of quantum state transmission to private communication and our subsequent joint work generalising this to entanglement/secret key distillation. These findings put into a new light the earlier observations (by Acin et al.and Bruss et al.) of qualitative equivalence between these two tasks, and also prepared the ground for the recent step forward by Horodecki et al., to formulate key distillation strictly within the LOCC paradigm and then to exhibit bound entangled states which nevertheless contain secret key. Contributed Talks Howard Barnum: Query complexity & semidefinite programming We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we do the following: We show that as far as query complexity is concerned, the workspace of a quantum computer used to evaluate f(x) by querying the bits of an n-bit string x can be limited to n + k, where f takes k bit strings as values. We give an algorithm that on input the truth table of a partial boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm that attempts to evaluate f in t queries. We use semidefinite programming duality to formulate a dual SDP Phat(f, t, e) that is feasible if and only if f cannot be avluated within error e by a t-step quantum query algorithm. Using this SDP we derive a general lower bound for query complexity that encompasses a lower bound method of Ambainis and its generalizations. We give an interpretation of the primal SDP as a generalized form of branching in quantum computation. (This is joint work with Mike Saks and Mario Szegedy.) Matthias Christandl: A new generic proof for the security of quantum key distribution We present a new proof for the security of quantum key distribution. The presented proof is general in nature and applies to prepare-and-measure protocols such as BB84 as well as entanglement-based quantum cryptography such as E91. We use techniques that do not relate to entanglement distillation and thus differ significantly from all known security proofs. In order to derive a general security threshold we apply the recent result on privacy amplification in the presence of a quantum mechanical adversary by König, Maurer and Renner (2003). (This is joint work with Artur Ekert and Renato Renner.) Christoph Durr: Quantum query complexity of some graph problems Quantum algorithms for graph problems are considered, both in the adjacency matrix query model and in an adjacency list-like array model. We give almost tight lower and upper bounds for Connectivity, Strong Connectivity, Minimum Spanning Tree and Single Source Shortest Paths. (This is joint work with Mark Heiligman, Peter Hoyer, Mehdi Mhalla, and Yahui Lei.) Ivette Fuentes-Guridi: Holonomic quantum computation in the presence of decoherence We investigate the effects of decoherence in the geometric evolution of states of a degenerate quantum system. This is done by generalizing the scheme for geometric phases in open systems to non-Abelian holonomies. The formalism is applied to estimate the errors produced by performing an universal set of holonomic quantum gates in the presence of an environment. We pinpoint the single source of error in the scheme that must be corrected to achieve holonomic quantum computation completely robust to decoherence. Aram Harrow: Coherent communication of classical messages I define coherent communication in terms of a simple primitive, show it is equivalent to the ability to send a classical message with a unitary or isometric operation, and use it to relate other resources in quantum information theory. Using coherent communication, I can generalize super-dense coding to prepare arbitrary quantum states instead of only classical messages. I also derive single-letter formulae for the classical and quantum capacities of a bipartite unitary gate assisted by an arbitrary fixed amount of entanglement per use. Louis Kauffman: Braiding operators and quantum computing This talk will prove that there is a universal set of gates for quantum computing consisting in A single unitary solution R to the Yang-Baxter equation. Local unitary single qubit operations. The matrix R is the change of basis matrix taking the standard basis of a 2-qubit vector space to the Bell basis. This matrix is not only a unitary solution to the Yang-Baxter equation, it also gives rise to an interesting invariant of knots and links. This talk will pivot on this Theorem and discuss relationships between braids, knots, topological and quantum entanglement and quantum computing. From the point of view of this Theorem, any quantum computer can be configured as representation of an element in a generalization of the Artin Braid group. (This is joint work with Sam Lomonaco.) Sophie Laplante: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments We prove a very general lower bound technique for quantum and randomized query complexity that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted, unweighted methods of Ambainis, and the spectral method of Barnum, Saks, and Szegedy. As an immediate consequence of our main theorem, adversary methods can only prove lower bounds for Boolean functions f in O(min(sqrt{n C0(f)}, sqrt{n C1(f)})), where C0, C1 is the certificate complexity, and n is the size of the input. We also derive a general form of the ad hoc weighted method used by Hoyer, Neerbek, and Shi to give a quantum lower bound on ordered search and sorting. Reference: quant-ph/0311189 (This is joint work with Frederic Magniez.) David Poulin: Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect We present an efficient quantum algorithm to measure the average fidelity decay of a quantum map under perturbation using a single bit of quantum information. Our algorithm scales only as the complexity of the map under investigation, so for those maps admitting an efficient gate decomposition, it provides an exponential speed-up over known classical procedures. Fidelity decay is important in the study of complex dynamical systems, where it is conjectured to be a signature of quantum chaos. Our result also illustrates the role of chaos in the process of decoherence. Barry Sanders: Sharing secret quantum states: theory and experiment Threshold quantum secret sharing enables a quantum state to be transmitted to multiple players who cannot be trusted, whereas certain groups of players can be trusted. Quantum secrets may need to be shared for distributed quantum computing protocols, for quantum communication where trust is an issue, and for distributing quantum money, for example. I explain threshold quantum secret sharing, discuss continuous variable threshold quantum secret sharing, and present results of a recent successful threshold quantum secret sharing experiment implemented in a continuous variable system. Daniel Terno: Quantum information and special relativity Relativistic effects affect nearly all notions of quantum information theory. The vacuum behaves as a noisy channel, even if the detectors are perfect. The standard definition of a reduced density matrix fails for photon polarization because the transversality condition behaves like a superselection rule. We can, however, define an effective reduced density matrix which corresponds to a restricted class of positive operator-valued measures. There are no pure photon qubits, and no exactly orthogonal qubit states. Reduced density matrices for the spin of massive particles are well-defined, but are not covariant under Lorentz transformations. The spin entropy is not a relativistic scalar and has no invariant meaning. The distinguishability of quantum signals and their entanglement depend on the relative motion of observers. Posters Charlene Ahn Quantum error correction for continuously detected errors Muhammed Sabieh Anwar Preparing pure initial states from para-hydrogen Anne Braodbent Multi-party pseudo-telepathy Hilary Carteret Exact asymptotics for the quantum walk on the line Circuits for the direct detection of entanglement without the addition of noise Kai Chen A matrix realignment method for recognizing entanglement Donny Cheung Improved bounds for approximate quantum Fourier transforms Sora Choi Quantum key distribution network between various groups Igor Devatek Triple trade-offs in quantum Shannon theory Leonid Fedichkin Additivity of decoherence measures for multiqubit quantum systems Stephen Fenner Implementing the fanout gate by a Hamiltonian The power of constant-depth quantum circuits Fanout is hard to implement in constant with generalized Toffoli gates Jose Fernandez Quantum circuits for discrete logarithms on Galois Fields Theoretical methods and experimental implementations of non-adiabatic (heat bath) algorithmic cooling Ivette Fuentes-Guridi Holonomic quantum computation in the presence of decoherence Jim Harrington Local rules for protecting topological quantum memory Lawrence Ioannou Detecting entanglement with partial information Kazuo Iwama Quantum oracle computation with and without noises Phil Kaye Efficient implementation of quantum discrete logarithm algorithms on elliptic curves over extensions of GF(2) Viv Kendon Entanglement in Shor's algorithm Avanti Ketkar & Santosh Kumar Bounds on stabilizer codes over GF(q 2 ) Andreas Klappenecker Mutually unbiased bases Takeshi Koshiba Characterizing the existence of quantum one-way permutations Jozef Kosik Scattering model of quantum random walk Vasilijs Kravcevs Boolean function computation by probabilistic and quantum decision trees Maksim Kravtsev Models of probabilistic reversible automata and quantum counterparts Keiji Matsumoto Additivity of Holevo capacity and strong converse of channel capacity and entanglement dilution Carlos Mochon Computing with anyons Masoud Mohseni Optical realization of optimal unambiguous discrimination for pure and mixed quantum states Mio Murao LOCC extraction of distributed quantum information Falk Niehoerster & Helge Rose The Fraunhofer Quantum Computing Services - A parallel simulator of quantum computing processes Harold Ollivier Quantum convolutional coding Tobias Osborne The propagation of quantum information through a spin system Michel Pioro-Ladriere Electron Spin based qubits in lateral gated quantum dots Sergio de Rinaldis Distinguishability of complete and unextendible product bases David Roberts Non-local correlations as information theoretic resources Jeremie Roland Robustness to noise of Hamiltonian search algorithms David Santos Optimal strategies in quantum message authentication Toshiyuki Shimono Numerical test of superadditivity of entanglement of formation for four-qubit states Marcus Silva Erasure thresholds for efficient linear optics quantum computing Graeme Smith Efficient multiparty quantum data hiding Won Min Son D-outcome measurement for a nonlocality test Rob Spekkens The cryptographic power of private shared reference frames Krysta Svore Compiling quantum computations into elementary operations Christino Tamon A note on graphs resistant to quantum uniform mixing Yuuki Tokunaga Anonymous quantum cash Ben Toner Quantifying and generalizing the Kochen-Specker theorem Nicholas Whitlock A theory for matter-wave detection | invited | — | 50 | Frédéric Magniez | — |
| Holonomic quantum computation in the presence of decoherence | regular | — | 15 | Ivette Fuentes-Guridi | — |
| Quantum information and special relativity | regular | — | 15 | Daniel Terno | — |
Posters Charlene
Ahn Quantum
error correction for continuously detected errors Muhammed Sabieh
Anwar Preparing
pure initial states from para-hydrogen Anne Braodbent Multi-party
pseudo-telepathy Hilary Carteret Exact asymptotics
for the quantum walk on the line Circuits for the direct detection of entanglement without the addition of
noise Kai Chen A matrix realignment
method for recognizing entanglement Donny Cheung Improved bounds
for approximate quantum Fourier transforms Sora Choi Quantum key
distribution network between various groups Igor Devatek Triple trade-offs
in quantum Shannon theory Leonid Fedichkin Additivity
of decoherence measures for multiqubit quantum systems Stephen Fenner Implementing
the fanout gate by a Hamiltonian The power of constant-depth quantum circuits Fanout is hard to implement in constant with generalized Toffoli gates Jose Fernandez Quantum circuits
for discrete logarithms on Galois Fields Theoretical methods and experimental implementations of non-adiabatic (heat bath) algorithmic cooling Ivette Fuentes-Guridi Holonomic quantum computation in the presence of decoherence Jim Harrington Local rules
for protecting topological quantum memory Lawrence Ioannou Detecting
entanglement with partial information Kazuo Iwama Quantum oracle
computation with and without noises Phil Kaye Efficient
implementation of quantum discrete logarithm algorithms on elliptic curves over extensions of GF(2) Viv Kendon Entanglement
in Shor's algorithm Avanti Ketkar
& Santosh Kumar Bounds on
stabilizer codes over GF(q 2 ) Andreas Klappenecker Mutually unbiased
bases Takeshi Koshiba Characterizing
the existence of quantum one-way permutations Jozef Kosik Scattering
model of quantum random walk Vasilijs Kravcevs Boolean function
computation by probabilistic and quantum decision trees Maksim Kravtsev Models of
probabilistic reversible automata and quantum counterparts Keiji Matsumoto Additivity
of Holevo capacity and strong converse of channel capacity and entanglement
dilution Carlos Mochon Computing
with anyons Masoud Mohseni Optical realization
of optimal unambiguous discrimination for pure and mixed quantum states Mio Murao LOCC extraction
of distributed quantum information Falk Niehoerster
& Helge Rose The Fraunhofer
Quantum Computing Services - A parallel simulator of quantum computing processes Harold Ollivier Quantum convolutional
coding Tobias Osborne The propagation
of quantum information through a spin system Michel Pioro-Ladriere Electron Spin
based qubits in lateral gated quantum dots Sergio de Rinaldis Distinguishability of complete and unextendible product bases David Roberts Non-local correlations as information theoretic resources Jeremie Roland Robustness
to noise of Hamiltonian search algorithms David Santos Optimal strategies
in quantum message authentication Toshiyuki
Shimono Numerical
test of superadditivity of entanglement of formation for four-qubit states Marcus Silva Erasure thresholds
for efficient linear optics quantum computing Graeme Smith Efficient
multiparty quantum data hiding Won Min Son D-outcome
measurement for a nonlocality test Rob Spekkens The cryptographic
power of private shared reference frames Krysta Svore Compiling
quantum computations into elementary operations Christino
Tamon A note on
graphs resistant to quantum uniform mixing Yuuki Tokunaga Anonymous
quantum cash Ben Toner Quantifying
and generalizing the Kochen-Specker theorem Nicholas Whitlock A theory for
matter-wave detection |
|||||
| Braiding operators and quantum computing | regular | — | 15 | Louis Kauffman | — |
A single unitary solution R to the Yang-Baxter equation. Local unitary single qubit operations. |
|||||
| invited | — | 115 | Poster Session | — | |
| Quantum query complexity of some graph problems | regular | — | 15 | Christoph Dürr | — |
| Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size | invited | — | 50 | Ran Raz | — |
| Symmetric group problems | invited | — | 50 | Julia Kempe | — |
| Query complexity & semidefinite programming | regular | — | 15 | Howard Barnum | — |
We show that as far as query complexity is concerned, the workspace of a quantum computer used to evaluate f(x) by querying the bits of an n-bit string x can be limited to
n + k, where f takes k bit strings as values. We give an algorithm that on input the truth table of a partial boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm that attempts to evaluate f in t queries. We use semidefinite programming duality to formulate a dual SDP Phat(f, t, e) that is feasible if and only if f cannot be avluated within error e by a t-step quantum query algorithm. Using this SDP we derive a general lower bound for query complexity that encompasses a lower bound method of Ambainis and its generalizations. We give an interpretation of the primal SDP as a generalized form of branching in quantum computation. |
|||||
| Lower bounds for randomized and quantum query complexity using Kolmogorov arguments | regular | — | 15 | Sophie Laplante | — |
| A subexponential-time quantum algorithm for the dihedral hidden subgroup problem Debbie Leung: Applications of the quantum composability theorem Frederic Magniez: Quantum Algorithms for the Triangle Problem We present two new quantum algorithms that either finds a triangle in an undirected graph G on n nodes, or rejects if G is triangle free. The first algorithm uses combinatorial ideas with Grover Search and makes \tilde{O}(n^{10/7}) queries. The second algorithm uses O(n^{13/10}) queries, and it is based on a new design concept of Ambainis that incorporates the benefits of quantum walks into Grover search. The first algorithm uses only O(log n) qubits in its quantum subroutines, whereas the second one uses O(n) qubits. Note: joint work with Miklos Santha and Mario Szegedy Serge Massar: Non locality We describe the geometry of the space of non local correlations and we show how it is possible to interconvert between different types of non local correlations. This should form the basis for developping an information theory of non local correlations. Ueli Maurer: On the Power of Quantum Memory A qubit can be used to implement a classical memory bit, but not vice versa. We address the question whether quantum memory can be more powerful than classical memory in a classical information context where some relevant information X (e.g. an n-bit string) must be stored in memory of insufficient size s (e.g. s We discuss an information-theoretic model of memory, which includes quantum memory, and show that in a quite general context, quantum memory is only marginally more powerful than classical memory. In particular, classical privacy amplification by universal hashing remains secure even against an adversary with (the same amount of) quantum rather than classical memory. It remains a general open problem to prove certain classical information-theoretic cryptosystems, for instance schemes secure in the bounded-storage model, secure in presence of a quantum adversary. This is joint work with Robert Koenig and Renato Renner. Jaikumar Radhakrishnan: The bounded-round quantum communication complexity of set disjointness In the set disjointness problem, there are two parties A and B, each with a subset of {1,...,n}. They wish to communicate to determine if their sets are disjoint. For this problem quantum protocols do provably better than classical protocols. Recently, Aaronson and Ambainis showed a protocol for this problem where the two parties exchange O(sqrt{n}) qubits, matching the previous lower bound of Omega(sqrt{n}) shown by Razborov. (The classical randomized communication complexity of this problem is theta(n).) We consider bounded-round quantum communication protocols for the set disjointness problem, and show that in any communication protocol with k rounds, the two parties must exchange Omega(n/k^2) qubits. This lower bound is obtained by adapting the the information theoretic proof technique of Bar-Yossef, Jayram, Kumar and Sivakumar to the quantum setting. An upper bound of O(n/k) follows easily from the O(sqrt{n}) upper bound due to Aaronson and Ambainis. For protocols with no restriction on the number of rounds, we can conclude that the two parties must exchange Omega(n^{1/3}) qubits. This, however, falls short of the optimal Omega(sqrt{n}) lower bound shown by Razborov. Ran Raz: Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size I will talk about recent lower bounds for multi-linear arithmetic formulas. A surprising and beautiful application of these bounds in the field of quantum computation was recently found by Scott Aaronson [Scott Aaronson, "Multilinear Formulas and Skepticism of Quantum Computing"], and will be discussed in his talk. In my talk, I plan to give a short introduction to the problem as well as the main ideas of the lower bounds proof. Some more details are given below: Arithmetic formulas for computing the determinant and the permanent of a matrix have been studied since the 19th century. Are there polynomial size formulas for these functions? Although the determinant and the permanent are among the most extensively studied computational problems, polynomial size formulas for these functions are not known. An outstanding open problem in complexity theory is to prove that polynomial size formulas for these functions do not exist. Note, however, that super-polynomial lower bounds for the size of arithmetic formulas are not known for any explicit function and that questions of this type are considered to be among the most challenging open problems in theoretical computer science. An arithmetic formula is multi-linear if the polynomial computed by each of its sub-formulas is multi-linear, that is, in each of its monomials the power of every input variable is at most one. Multi-linear formulas are restricted, as they do not allow the intermediate use of higher powers of variables in order to finally compute a certain multi-linear function. Note, however, that for many multi-linear functions, formulas that are not multi-linear are very counter-intuitive. Note also that both the determinant and the permanent are multi-linear functions and that many of the well known formulas for these functions are multi-linear formulas. We prove that any multi-linear arithmetic formula for the determinant or the permanent of an n dimensional matrix is of size super-polynomial in n. Previously, no lower bound was known (for any explicit function) even for the special case of multi-linear formulas of constant depth. Oded Regev: Recent connections between quantum computation and lattice problems I will describe a result obtained together with Dorit Aharonov on lattice problems in quantum NP and a more recent result showing how to dequantize the construction in order to obtain containment in NP. Time permitting, I will also comment on the possibility of applying Kuperberg's algorithm to solve lattice problems in subexponential time. Alex Russell: Quantum Computation in Groups This talk will survey some recent developments in the theory of quantum computation in groups, focusing on two primary research efforts: development of efficient quantum Fourier transforms and development of efficient solutions to hidden subgroup problems. Quantum Fourier transforms. The talk will describe a "quantization" of the successful separation of variables technique, the generic framework responsible for most known efficient classical Fourier transform algorithms. This results in a wide family of efficient quantum circuits for the quantum Fourier transform, recovering all known efficient quantum Fourier transforms and providing efficient transforms for many new groups. In addition, it gives the first subexponential quantum circuits for the Fourier transform over several interesting linear groups. Hidden subgroup problems. The talk will discuss some recent advances in our understand of the hidden subgroup problems, discussing new closure properties and solutions for families of groups which appear to require the strong standard method. Leonard Schulman Physical limits of heat-bath algorithmic cooling Peter Shor: Additivity questions in quantum information theory There are a number of interesting, open additivity questions in quantum information theory. Recently, I have been able to show that some of these are equivalent. I will discuss open additivity questions in general and this proof of equivalence in particular. Kiyoshi Tamaki: Unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel We prove the unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel. We assume that Alice has an ideal single photon source and Bob has detectors that discriminate between single photon states on one hand and vacuum state or multiphoton states on the other hand. We use a reduction to an entanglement distillation protocol initiated by a local filtering process in our proof. The bit errors and the phase errors are correlated after the filtering, and we can bound the amount of phase errors from the observed bit errors by an estimation method involving nonorthogonal measurements. Leslie Valiant: Holographic Algorithms John Watrous: Stronger Error Reduction for QMA The complexity class QMA is a bounded-error quantum computational variant of the class NP, where a quantum state plays the role of a certificate. It is known that the error of a given QMA protocol can be reduced exponentially at the cost of a polynomial increase in the length of the certificate. In this talk, I will prove that such a reduction in error is in fact possible with no increase in the length of the certificate whatsoever. Applications of this fact include a proof that logarithmic-length quantum certificates give no increase in power over BQP and a simple proof that QMA is contained in the class PP. Andreas Winter: From entanglement to secret key and back The last year has seen a series of dramatic progresses in the areas of quantum channel capacities, entanglement distillation and our understanding of how these problems relate to secret communication. In this talk I will first review the analogy between the theories of entanglement and key distillation. Then I go on to explain the elements of the recent progress, first describing Devetak's recent reduction of quantum state transmission to private communication and our subsequent joint work generalising this to entanglement/secret key distillation. These findings put into a new light the earlier observations (by Acin et al.and Bruss et al.) of qualitative equivalence between these two tasks, and also prepared the ground for the recent step forward by Horodecki et al., to formulate key distillation strictly within the LOCC paradigm and then to exhibit bound entangled states which nevertheless contain secret key. Contributed Talks Howard Barnum: Query complexity & semidefinite programming We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we do the following: We show that as far as query complexity is concerned, the workspace of a quantum computer used to evaluate f(x) by querying the bits of an n-bit string x can be limited to n + k, where f takes k bit strings as values. We give an algorithm that on input the truth table of a partial boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm that attempts to evaluate f in t queries. We use semidefinite programming duality to formulate a dual SDP Phat(f, t, e) that is feasible if and only if f cannot be avluated within error e by a t-step quantum query algorithm. Using this SDP we derive a general lower bound for query complexity that encompasses a lower bound method of Ambainis and its generalizations. We give an interpretation of the primal SDP as a generalized form of branching in quantum computation. (This is joint work with Mike Saks and Mario Szegedy.) Matthias Christandl: A new generic proof for the security of quantum key distribution We present a new proof for the security of quantum key distribution. The presented proof is general in nature and applies to prepare-and-measure protocols such as BB84 as well as entanglement-based quantum cryptography such as E91. We use techniques that do not relate to entanglement distillation and thus differ significantly from all known security proofs. In order to derive a general security threshold we apply the recent result on privacy amplification in the presence of a quantum mechanical adversary by König, Maurer and Renner (2003). (This is joint work with Artur Ekert and Renato Renner.) Christoph Durr: Quantum query complexity of some graph problems Quantum algorithms for graph problems are considered, both in the adjacency matrix query model and in an adjacency list-like array model. We give almost tight lower and upper bounds for Connectivity, Strong Connectivity, Minimum Spanning Tree and Single Source Shortest Paths. (This is joint work with Mark Heiligman, Peter Hoyer, Mehdi Mhalla, and Yahui Lei.) Ivette Fuentes-Guridi: Holonomic quantum computation in the presence of decoherence We investigate the effects of decoherence in the geometric evolution of states of a degenerate quantum system. This is done by generalizing the scheme for geometric phases in open systems to non-Abelian holonomies. The formalism is applied to estimate the errors produced by performing an universal set of holonomic quantum gates in the presence of an environment. We pinpoint the single source of error in the scheme that must be corrected to achieve holonomic quantum computation completely robust to decoherence. Aram Harrow: Coherent communication of classical messages I define coherent communication in terms of a simple primitive, show it is equivalent to the ability to send a classical message with a unitary or isometric operation, and use it to relate other resources in quantum information theory. Using coherent communication, I can generalize super-dense coding to prepare arbitrary quantum states instead of only classical messages. I also derive single-letter formulae for the classical and quantum capacities of a bipartite unitary gate assisted by an arbitrary fixed amount of entanglement per use. Louis Kauffman: Braiding operators and quantum computing This talk will prove that there is a universal set of gates for quantum computing consisting in A single unitary solution R to the Yang-Baxter equation. Local unitary single qubit operations. The matrix R is the change of basis matrix taking the standard basis of a 2-qubit vector space to the Bell basis. This matrix is not only a unitary solution to the Yang-Baxter equation, it also gives rise to an interesting invariant of knots and links. This talk will pivot on this Theorem and discuss relationships between braids, knots, topological and quantum entanglement and quantum computing. From the point of view of this Theorem, any quantum computer can be configured as representation of an element in a generalization of the Artin Braid group. (This is joint work with Sam Lomonaco.) Sophie Laplante: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments We prove a very general lower bound technique for quantum and randomized query complexity that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted, unweighted methods of Ambainis, and the spectral method of Barnum, Saks, and Szegedy. As an immediate consequence of our main theorem, adversary methods can only prove lower bounds for Boolean functions f in O(min(sqrt{n C0(f)}, sqrt{n C1(f)})), where C0, C1 is the certificate complexity, and n is the size of the input. We also derive a general form of the ad hoc weighted method used by Hoyer, Neerbek, and Shi to give a quantum lower bound on ordered search and sorting. Reference: quant-ph/0311189 (This is joint work with Frederic Magniez.) David Poulin: Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect We present an efficient quantum algorithm to measure the average fidelity decay of a quantum map under perturbation using a single bit of quantum information. Our algorithm scales only as the complexity of the map under investigation, so for those maps admitting an efficient gate decomposition, it provides an exponential speed-up over known classical procedures. Fidelity decay is important in the study of complex dynamical systems, where it is conjectured to be a signature of quantum chaos. Our result also illustrates the role of chaos in the process of decoherence. Barry Sanders: Sharing secret quantum states: theory and experiment Threshold quantum secret sharing enables a quantum state to be transmitted to multiple players who cannot be trusted, whereas certain groups of players can be trusted. Quantum secrets may need to be shared for distributed quantum computing protocols, for quantum communication where trust is an issue, and for distributing quantum money, for example. I explain threshold quantum secret sharing, discuss continuous variable threshold quantum secret sharing, and present results of a recent successful threshold quantum secret sharing experiment implemented in a continuous variable system. Daniel Terno: Quantum information and special relativity Relativistic effects affect nearly all notions of quantum information theory. The vacuum behaves as a noisy channel, even if the detectors are perfect. The standard definition of a reduced density matrix fails for photon polarization because the transversality condition behaves like a superselection rule. We can, however, define an effective reduced density matrix which corresponds to a restricted class of positive operator-valued measures. There are no pure photon qubits, and no exactly orthogonal qubit states. Reduced density matrices for the spin of massive particles are well-defined, but are not covariant under Lorentz transformations. The spin entropy is not a relativistic scalar and has no invariant meaning. The distinguishability of quantum signals and their entanglement depend on the relative motion of observers. Posters Charlene Ahn Quantum error correction for continuously detected errors Muhammed Sabieh Anwar Preparing pure initial states from para-hydrogen Anne Braodbent Multi-party pseudo-telepathy Hilary Carteret Exact asymptotics for the quantum walk on the line Circuits for the direct detection of entanglement without the addition of noise Kai Chen A matrix realignment method for recognizing entanglement Donny Cheung Improved bounds for approximate quantum Fourier transforms Sora Choi Quantum key distribution network between various groups Igor Devatek Triple trade-offs in quantum Shannon theory Leonid Fedichkin Additivity of decoherence measures for multiqubit quantum systems Stephen Fenner Implementing the fanout gate by a Hamiltonian The power of constant-depth quantum circuits Fanout is hard to implement in constant with generalized Toffoli gates Jose Fernandez Quantum circuits for discrete logarithms on Galois Fields Theoretical methods and experimental implementations of non-adiabatic (heat bath) algorithmic cooling Ivette Fuentes-Guridi Holonomic quantum computation in the presence of decoherence Jim Harrington Local rules for protecting topological quantum memory Lawrence Ioannou Detecting entanglement with partial information Kazuo Iwama Quantum oracle computation with and without noises Phil Kaye Efficient implementation of quantum discrete logarithm algorithms on elliptic curves over extensions of GF(2) Viv Kendon Entanglement in Shor's algorithm Avanti Ketkar & Santosh Kumar Bounds on stabilizer codes over GF(q 2 ) Andreas Klappenecker Mutually unbiased bases Takeshi Koshiba Characterizing the existence of quantum one-way permutations Jozef Kosik Scattering model of quantum random walk Vasilijs Kravcevs Boolean function computation by probabilistic and quantum decision trees Maksim Kravtsev Models of probabilistic reversible automata and quantum counterparts Keiji Matsumoto Additivity of Holevo capacity and strong converse of channel capacity and entanglement dilution Carlos Mochon Computing with anyons Masoud Mohseni Optical realization of optimal unambiguous discrimination for pure and mixed quantum states Mio Murao LOCC extraction of distributed quantum information Falk Niehoerster & Helge Rose The Fraunhofer Quantum Computing Services - A parallel simulator of quantum computing processes Harold Ollivier Quantum convolutional coding Tobias Osborne The propagation of quantum information through a spin system Michel Pioro-Ladriere Electron Spin based qubits in lateral gated quantum dots Sergio de Rinaldis Distinguishability of complete and unextendible product bases David Roberts Non-local correlations as information theoretic resources Jeremie Roland Robustness to noise of Hamiltonian search algorithms David Santos Optimal strategies in quantum message authentication Toshiyuki Shimono Numerical test of superadditivity of entanglement of formation for four-qubit states Marcus Silva Erasure thresholds for efficient linear optics quantum computing Graeme Smith Efficient multiparty quantum data hiding Won Min Son D-outcome measurement for a nonlocality test Rob Spekkens The cryptographic power of private shared reference frames Krysta Svore Compiling quantum computations into elementary operations Christino Tamon A note on graphs resistant to quantum uniform mixing Yuuki Tokunaga Anonymous quantum cash Ben Toner Quantifying and generalizing the Kochen-Specker theorem Nicholas Whitlock A theory for matter-wave detection | invited | — | 50 | Greg Kuperberg | — |
| On the Power of Quantum Memory A qubit can be used to implement a classical memory bit, but not vice versa. We address the question whether quantum memory can be more powerful than classical memory in a classical information context where some relevant information X (e.g. an n-bit string) must be stored in memory of insufficient size s (e.g. s We discuss an information-theoretic model of memory, which includes quantum memory, and show that in a quite general context, quantum memory is only marginally more powerful than classical memory. In particular, classical privacy amplification by universal hashing remains secure even against an adversary with (the same amount of) quantum rather than classical memory. It remains a general open problem to prove certain classical information-theoretic cryptosystems, for instance schemes secure in the bounded-storage model, secure in presence of a quantum adversary. This is joint work with Robert Koenig and Renato Renner. Jaikumar Radhakrishnan: The bounded-round quantum communication complexity of set disjointness In the set disjointness problem, there are two parties A and B, each with a subset of {1,...,n}. They wish to communicate to determine if their sets are disjoint. For this problem quantum protocols do provably better than classical protocols. Recently, Aaronson and Ambainis showed a protocol for this problem where the two parties exchange O(sqrt{n}) qubits, matching the previous lower bound of Omega(sqrt{n}) shown by Razborov. (The classical randomized communication complexity of this problem is theta(n).) We consider bounded-round quantum communication protocols for the set disjointness problem, and show that in any communication protocol with k rounds, the two parties must exchange Omega(n/k^2) qubits. This lower bound is obtained by adapting the the information theoretic proof technique of Bar-Yossef, Jayram, Kumar and Sivakumar to the quantum setting. An upper bound of O(n/k) follows easily from the O(sqrt{n}) upper bound due to Aaronson and Ambainis. For protocols with no restriction on the number of rounds, we can conclude that the two parties must exchange Omega(n^{1/3}) qubits. This, however, falls short of the optimal Omega(sqrt{n}) lower bound shown by Razborov. Ran Raz: Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size I will talk about recent lower bounds for multi-linear arithmetic formulas. A surprising and beautiful application of these bounds in the field of quantum computation was recently found by Scott Aaronson [Scott Aaronson, "Multilinear Formulas and Skepticism of Quantum Computing"], and will be discussed in his talk. In my talk, I plan to give a short introduction to the problem as well as the main ideas of the lower bounds proof. Some more details are given below: Arithmetic formulas for computing the determinant and the permanent of a matrix have been studied since the 19th century. Are there polynomial size formulas for these functions? Although the determinant and the permanent are among the most extensively studied computational problems, polynomial size formulas for these functions are not known. An outstanding open problem in complexity theory is to prove that polynomial size formulas for these functions do not exist. Note, however, that super-polynomial lower bounds for the size of arithmetic formulas are not known for any explicit function and that questions of this type are considered to be among the most challenging open problems in theoretical computer science. An arithmetic formula is multi-linear if the polynomial computed by each of its sub-formulas is multi-linear, that is, in each of its monomials the power of every input variable is at most one. Multi-linear formulas are restricted, as they do not allow the intermediate use of higher powers of variables in order to finally compute a certain multi-linear function. Note, however, that for many multi-linear functions, formulas that are not multi-linear are very counter-intuitive. Note also that both the determinant and the permanent are multi-linear functions and that many of the well known formulas for these functions are multi-linear formulas. We prove that any multi-linear arithmetic formula for the determinant or the permanent of an n dimensional matrix is of size super-polynomial in n. Previously, no lower bound was known (for any explicit function) even for the special case of multi-linear formulas of constant depth. Oded Regev: Recent connections between quantum computation and lattice problems I will describe a result obtained together with Dorit Aharonov on lattice problems in quantum NP and a more recent result showing how to dequantize the construction in order to obtain containment in NP. Time permitting, I will also comment on the possibility of applying Kuperberg's algorithm to solve lattice problems in subexponential time. Alex Russell: Quantum Computation in Groups This talk will survey some recent developments in the theory of quantum computation in groups, focusing on two primary research efforts: development of efficient quantum Fourier transforms and development of efficient solutions to hidden subgroup problems. Quantum Fourier transforms. The talk will describe a "quantization" of the successful separation of variables technique, the generic framework responsible for most known efficient classical Fourier transform algorithms. This results in a wide family of efficient quantum circuits for the quantum Fourier transform, recovering all known efficient quantum Fourier transforms and providing efficient transforms for many new groups. In addition, it gives the first subexponential quantum circuits for the Fourier transform over several interesting linear groups. Hidden subgroup problems. The talk will discuss some recent advances in our understand of the hidden subgroup problems, discussing new closure properties and solutions for families of groups which appear to require the strong standard method. Leonard Schulman Physical limits of heat-bath algorithmic cooling Peter Shor: Additivity questions in quantum information theory There are a number of interesting, open additivity questions in quantum information theory. Recently, I have been able to show that some of these are equivalent. I will discuss open additivity questions in general and this proof of equivalence in particular. Kiyoshi Tamaki: Unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel We prove the unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel. We assume that Alice has an ideal single photon source and Bob has detectors that discriminate between single photon states on one hand and vacuum state or multiphoton states on the other hand. We use a reduction to an entanglement distillation protocol initiated by a local filtering process in our proof. The bit errors and the phase errors are correlated after the filtering, and we can bound the amount of phase errors from the observed bit errors by an estimation method involving nonorthogonal measurements. Leslie Valiant: Holographic Algorithms John Watrous: Stronger Error Reduction for QMA The complexity class QMA is a bounded-error quantum computational variant of the class NP, where a quantum state plays the role of a certificate. It is known that the error of a given QMA protocol can be reduced exponentially at the cost of a polynomial increase in the length of the certificate. In this talk, I will prove that such a reduction in error is in fact possible with no increase in the length of the certificate whatsoever. Applications of this fact include a proof that logarithmic-length quantum certificates give no increase in power over BQP and a simple proof that QMA is contained in the class PP. Andreas Winter: From entanglement to secret key and back The last year has seen a series of dramatic progresses in the areas of quantum channel capacities, entanglement distillation and our understanding of how these problems relate to secret communication. In this talk I will first review the analogy between the theories of entanglement and key distillation. Then I go on to explain the elements of the recent progress, first describing Devetak's recent reduction of quantum state transmission to private communication and our subsequent joint work generalising this to entanglement/secret key distillation. These findings put into a new light the earlier observations (by Acin et al.and Bruss et al.) of qualitative equivalence between these two tasks, and also prepared the ground for the recent step forward by Horodecki et al., to formulate key distillation strictly within the LOCC paradigm and then to exhibit bound entangled states which nevertheless contain secret key. Contributed Talks Howard Barnum: Query complexity & semidefinite programming We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we do the following: We show that as far as query complexity is concerned, the workspace of a quantum computer used to evaluate f(x) by querying the bits of an n-bit string x can be limited to n + k, where f takes k bit strings as values. We give an algorithm that on input the truth table of a partial boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm that attempts to evaluate f in t queries. We use semidefinite programming duality to formulate a dual SDP Phat(f, t, e) that is feasible if and only if f cannot be avluated within error e by a t-step quantum query algorithm. Using this SDP we derive a general lower bound for query complexity that encompasses a lower bound method of Ambainis and its generalizations. We give an interpretation of the primal SDP as a generalized form of branching in quantum computation. (This is joint work with Mike Saks and Mario Szegedy.) Matthias Christandl: A new generic proof for the security of quantum key distribution We present a new proof for the security of quantum key distribution. The presented proof is general in nature and applies to prepare-and-measure protocols such as BB84 as well as entanglement-based quantum cryptography such as E91. We use techniques that do not relate to entanglement distillation and thus differ significantly from all known security proofs. In order to derive a general security threshold we apply the recent result on privacy amplification in the presence of a quantum mechanical adversary by König, Maurer and Renner (2003). (This is joint work with Artur Ekert and Renato Renner.) Christoph Durr: Quantum query complexity of some graph problems Quantum algorithms for graph problems are considered, both in the adjacency matrix query model and in an adjacency list-like array model. We give almost tight lower and upper bounds for Connectivity, Strong Connectivity, Minimum Spanning Tree and Single Source Shortest Paths. (This is joint work with Mark Heiligman, Peter Hoyer, Mehdi Mhalla, and Yahui Lei.) Ivette Fuentes-Guridi: Holonomic quantum computation in the presence of decoherence We investigate the effects of decoherence in the geometric evolution of states of a degenerate quantum system. This is done by generalizing the scheme for geometric phases in open systems to non-Abelian holonomies. The formalism is applied to estimate the errors produced by performing an universal set of holonomic quantum gates in the presence of an environment. We pinpoint the single source of error in the scheme that must be corrected to achieve holonomic quantum computation completely robust to decoherence. Aram Harrow: Coherent communication of classical messages I define coherent communication in terms of a simple primitive, show it is equivalent to the ability to send a classical message with a unitary or isometric operation, and use it to relate other resources in quantum information theory. Using coherent communication, I can generalize super-dense coding to prepare arbitrary quantum states instead of only classical messages. I also derive single-letter formulae for the classical and quantum capacities of a bipartite unitary gate assisted by an arbitrary fixed amount of entanglement per use. Louis Kauffman: Braiding operators and quantum computing This talk will prove that there is a universal set of gates for quantum computing consisting in A single unitary solution R to the Yang-Baxter equation. Local unitary single qubit operations. The matrix R is the change of basis matrix taking the standard basis of a 2-qubit vector space to the Bell basis. This matrix is not only a unitary solution to the Yang-Baxter equation, it also gives rise to an interesting invariant of knots and links. This talk will pivot on this Theorem and discuss relationships between braids, knots, topological and quantum entanglement and quantum computing. From the point of view of this Theorem, any quantum computer can be configured as representation of an element in a generalization of the Artin Braid group. (This is joint work with Sam Lomonaco.) Sophie Laplante: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments We prove a very general lower bound technique for quantum and randomized query complexity that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted, unweighted methods of Ambainis, and the spectral method of Barnum, Saks, and Szegedy. As an immediate consequence of our main theorem, adversary methods can only prove lower bounds for Boolean functions f in O(min(sqrt{n C0(f)}, sqrt{n C1(f)})), where C0, C1 is the certificate complexity, and n is the size of the input. We also derive a general form of the ad hoc weighted method used by Hoyer, Neerbek, and Shi to give a quantum lower bound on ordered search and sorting. Reference: quant-ph/0311189 (This is joint work with Frederic Magniez.) David Poulin: Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect We present an efficient quantum algorithm to measure the average fidelity decay of a quantum map under perturbation using a single bit of quantum information. Our algorithm scales only as the complexity of the map under investigation, so for those maps admitting an efficient gate decomposition, it provides an exponential speed-up over known classical procedures. Fidelity decay is important in the study of complex dynamical systems, where it is conjectured to be a signature of quantum chaos. Our result also illustrates the role of chaos in the process of decoherence. Barry Sanders: Sharing secret quantum states: theory and experiment Threshold quantum secret sharing enables a quantum state to be transmitted to multiple players who cannot be trusted, whereas certain groups of players can be trusted. Quantum secrets may need to be shared for distributed quantum computing protocols, for quantum communication where trust is an issue, and for distributing quantum money, for example. I explain threshold quantum secret sharing, discuss continuous variable threshold quantum secret sharing, and present results of a recent successful threshold quantum secret sharing experiment implemented in a continuous variable system. Daniel Terno: Quantum information and special relativity Relativistic effects affect nearly all notions of quantum information theory. The vacuum behaves as a noisy channel, even if the detectors are perfect. The standard definition of a reduced density matrix fails for photon polarization because the transversality condition behaves like a superselection rule. We can, however, define an effective reduced density matrix which corresponds to a restricted class of positive operator-valued measures. There are no pure photon qubits, and no exactly orthogonal qubit states. Reduced density matrices for the spin of massive particles are well-defined, but are not covariant under Lorentz transformations. The spin entropy is not a relativistic scalar and has no invariant meaning. The distinguishability of quantum signals and their entanglement depend on the relative motion of observers. Posters Charlene Ahn Quantum error correction for continuously detected errors Muhammed Sabieh Anwar Preparing pure initial states from para-hydrogen Anne Braodbent Multi-party pseudo-telepathy Hilary Carteret Exact asymptotics for the quantum walk on the line Circuits for the direct detection of entanglement without the addition of noise Kai Chen A matrix realignment method for recognizing entanglement Donny Cheung Improved bounds for approximate quantum Fourier transforms Sora Choi Quantum key distribution network between various groups Igor Devatek Triple trade-offs in quantum Shannon theory Leonid Fedichkin Additivity of decoherence measures for multiqubit quantum systems Stephen Fenner Implementing the fanout gate by a Hamiltonian The power of constant-depth quantum circuits Fanout is hard to implement in constant with generalized Toffoli gates Jose Fernandez Quantum circuits for discrete logarithms on Galois Fields Theoretical methods and experimental implementations of non-adiabatic (heat bath) algorithmic cooling Ivette Fuentes-Guridi Holonomic quantum computation in the presence of decoherence Jim Harrington Local rules for protecting topological quantum memory Lawrence Ioannou Detecting entanglement with partial information Kazuo Iwama Quantum oracle computation with and without noises Phil Kaye Efficient implementation of quantum discrete logarithm algorithms on elliptic curves over extensions of GF(2) Viv Kendon Entanglement in Shor's algorithm Avanti Ketkar & Santosh Kumar Bounds on stabilizer codes over GF(q 2 ) Andreas Klappenecker Mutually unbiased bases Takeshi Koshiba Characterizing the existence of quantum one-way permutations Jozef Kosik Scattering model of quantum random walk Vasilijs Kravcevs Boolean function computation by probabilistic and quantum decision trees Maksim Kravtsev Models of probabilistic reversible automata and quantum counterparts Keiji Matsumoto Additivity of Holevo capacity and strong converse of channel capacity and entanglement dilution Carlos Mochon Computing with anyons Masoud Mohseni Optical realization of optimal unambiguous discrimination for pure and mixed quantum states Mio Murao LOCC extraction of distributed quantum information Falk Niehoerster & Helge Rose The Fraunhofer Quantum Computing Services - A parallel simulator of quantum computing processes Harold Ollivier Quantum convolutional coding Tobias Osborne The propagation of quantum information through a spin system Michel Pioro-Ladriere Electron Spin based qubits in lateral gated quantum dots Sergio de Rinaldis Distinguishability of complete and unextendible product bases David Roberts Non-local correlations as information theoretic resources Jeremie Roland Robustness to noise of Hamiltonian search algorithms David Santos Optimal strategies in quantum message authentication Toshiyuki Shimono Numerical test of superadditivity of entanglement of formation for four-qubit states Marcus Silva Erasure thresholds for efficient linear optics quantum computing Graeme Smith Efficient multiparty quantum data hiding Won Min Son D-outcome measurement for a nonlocality test Rob Spekkens The cryptographic power of private shared reference frames Krysta Svore Compiling quantum computations into elementary operations Christino Tamon A note on graphs resistant to quantum uniform mixing Yuuki Tokunaga Anonymous quantum cash Ben Toner Quantifying and generalizing the Kochen-Specker theorem Nicholas Whitlock A theory for matter-wave detection | invited | — | 50 | Ueli Maurer | — |
| Recent connections between quantum computation and lattice problems | invited | — | 50 | Oded Regev | — |
| The bounded-round quantum communication complexity of set disjointness | invited | — | 50 | Jaikumar Radhakrishnan | — |
| Consequences and Limits of Nonlocal Strategies | invited | — | 50 | Richard Cleve | — |
| Applications of the quantum composability theorem Frederic Magniez: Quantum Algorithms for the Triangle Problem We present two new quantum algorithms that either finds a triangle in an undirected graph G on n nodes, or rejects if G is triangle free. The first algorithm uses combinatorial ideas with Grover Search and makes \tilde{O}(n^{10/7}) queries. The second algorithm uses O(n^{13/10}) queries, and it is based on a new design concept of Ambainis that incorporates the benefits of quantum walks into Grover search. The first algorithm uses only O(log n) qubits in its quantum subroutines, whereas the second one uses O(n) qubits. Note: joint work with Miklos Santha and Mario Szegedy Serge Massar: Non locality We describe the geometry of the space of non local correlations and we show how it is possible to interconvert between different types of non local correlations. This should form the basis for developping an information theory of non local correlations. Ueli Maurer: On the Power of Quantum Memory A qubit can be used to implement a classical memory bit, but not vice versa. We address the question whether quantum memory can be more powerful than classical memory in a classical information context where some relevant information X (e.g. an n-bit string) must be stored in memory of insufficient size s (e.g. s We discuss an information-theoretic model of memory, which includes quantum memory, and show that in a quite general context, quantum memory is only marginally more powerful than classical memory. In particular, classical privacy amplification by universal hashing remains secure even against an adversary with (the same amount of) quantum rather than classical memory. It remains a general open problem to prove certain classical information-theoretic cryptosystems, for instance schemes secure in the bounded-storage model, secure in presence of a quantum adversary. This is joint work with Robert Koenig and Renato Renner. Jaikumar Radhakrishnan: The bounded-round quantum communication complexity of set disjointness In the set disjointness problem, there are two parties A and B, each with a subset of {1,...,n}. They wish to communicate to determine if their sets are disjoint. For this problem quantum protocols do provably better than classical protocols. Recently, Aaronson and Ambainis showed a protocol for this problem where the two parties exchange O(sqrt{n}) qubits, matching the previous lower bound of Omega(sqrt{n}) shown by Razborov. (The classical randomized communication complexity of this problem is theta(n).) We consider bounded-round quantum communication protocols for the set disjointness problem, and show that in any communication protocol with k rounds, the two parties must exchange Omega(n/k^2) qubits. This lower bound is obtained by adapting the the information theoretic proof technique of Bar-Yossef, Jayram, Kumar and Sivakumar to the quantum setting. An upper bound of O(n/k) follows easily from the O(sqrt{n}) upper bound due to Aaronson and Ambainis. For protocols with no restriction on the number of rounds, we can conclude that the two parties must exchange Omega(n^{1/3}) qubits. This, however, falls short of the optimal Omega(sqrt{n}) lower bound shown by Razborov. Ran Raz: Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size I will talk about recent lower bounds for multi-linear arithmetic formulas. A surprising and beautiful application of these bounds in the field of quantum computation was recently found by Scott Aaronson [Scott Aaronson, "Multilinear Formulas and Skepticism of Quantum Computing"], and will be discussed in his talk. In my talk, I plan to give a short introduction to the problem as well as the main ideas of the lower bounds proof. Some more details are given below: Arithmetic formulas for computing the determinant and the permanent of a matrix have been studied since the 19th century. Are there polynomial size formulas for these functions? Although the determinant and the permanent are among the most extensively studied computational problems, polynomial size formulas for these functions are not known. An outstanding open problem in complexity theory is to prove that polynomial size formulas for these functions do not exist. Note, however, that super-polynomial lower bounds for the size of arithmetic formulas are not known for any explicit function and that questions of this type are considered to be among the most challenging open problems in theoretical computer science. An arithmetic formula is multi-linear if the polynomial computed by each of its sub-formulas is multi-linear, that is, in each of its monomials the power of every input variable is at most one. Multi-linear formulas are restricted, as they do not allow the intermediate use of higher powers of variables in order to finally compute a certain multi-linear function. Note, however, that for many multi-linear functions, formulas that are not multi-linear are very counter-intuitive. Note also that both the determinant and the permanent are multi-linear functions and that many of the well known formulas for these functions are multi-linear formulas. We prove that any multi-linear arithmetic formula for the determinant or the permanent of an n dimensional matrix is of size super-polynomial in n. Previously, no lower bound was known (for any explicit function) even for the special case of multi-linear formulas of constant depth. Oded Regev: Recent connections between quantum computation and lattice problems I will describe a result obtained together with Dorit Aharonov on lattice problems in quantum NP and a more recent result showing how to dequantize the construction in order to obtain containment in NP. Time permitting, I will also comment on the possibility of applying Kuperberg's algorithm to solve lattice problems in subexponential time. Alex Russell: Quantum Computation in Groups This talk will survey some recent developments in the theory of quantum computation in groups, focusing on two primary research efforts: development of efficient quantum Fourier transforms and development of efficient solutions to hidden subgroup problems. Quantum Fourier transforms. The talk will describe a "quantization" of the successful separation of variables technique, the generic framework responsible for most known efficient classical Fourier transform algorithms. This results in a wide family of efficient quantum circuits for the quantum Fourier transform, recovering all known efficient quantum Fourier transforms and providing efficient transforms for many new groups. In addition, it gives the first subexponential quantum circuits for the Fourier transform over several interesting linear groups. Hidden subgroup problems. The talk will discuss some recent advances in our understand of the hidden subgroup problems, discussing new closure properties and solutions for families of groups which appear to require the strong standard method. Leonard Schulman Physical limits of heat-bath algorithmic cooling Peter Shor: Additivity questions in quantum information theory There are a number of interesting, open additivity questions in quantum information theory. Recently, I have been able to show that some of these are equivalent. I will discuss open additivity questions in general and this proof of equivalence in particular. Kiyoshi Tamaki: Unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel We prove the unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel. We assume that Alice has an ideal single photon source and Bob has detectors that discriminate between single photon states on one hand and vacuum state or multiphoton states on the other hand. We use a reduction to an entanglement distillation protocol initiated by a local filtering process in our proof. The bit errors and the phase errors are correlated after the filtering, and we can bound the amount of phase errors from the observed bit errors by an estimation method involving nonorthogonal measurements. Leslie Valiant: Holographic Algorithms John Watrous: Stronger Error Reduction for QMA The complexity class QMA is a bounded-error quantum computational variant of the class NP, where a quantum state plays the role of a certificate. It is known that the error of a given QMA protocol can be reduced exponentially at the cost of a polynomial increase in the length of the certificate. In this talk, I will prove that such a reduction in error is in fact possible with no increase in the length of the certificate whatsoever. Applications of this fact include a proof that logarithmic-length quantum certificates give no increase in power over BQP and a simple proof that QMA is contained in the class PP. Andreas Winter: From entanglement to secret key and back The last year has seen a series of dramatic progresses in the areas of quantum channel capacities, entanglement distillation and our understanding of how these problems relate to secret communication. In this talk I will first review the analogy between the theories of entanglement and key distillation. Then I go on to explain the elements of the recent progress, first describing Devetak's recent reduction of quantum state transmission to private communication and our subsequent joint work generalising this to entanglement/secret key distillation. These findings put into a new light the earlier observations (by Acin et al.and Bruss et al.) of qualitative equivalence between these two tasks, and also prepared the ground for the recent step forward by Horodecki et al., to formulate key distillation strictly within the LOCC paradigm and then to exhibit bound entangled states which nevertheless contain secret key. Contributed Talks Howard Barnum: Query complexity & semidefinite programming We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we do the following: We show that as far as query complexity is concerned, the workspace of a quantum computer used to evaluate f(x) by querying the bits of an n-bit string x can be limited to n + k, where f takes k bit strings as values. We give an algorithm that on input the truth table of a partial boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm that attempts to evaluate f in t queries. We use semidefinite programming duality to formulate a dual SDP Phat(f, t, e) that is feasible if and only if f cannot be avluated within error e by a t-step quantum query algorithm. Using this SDP we derive a general lower bound for query complexity that encompasses a lower bound method of Ambainis and its generalizations. We give an interpretation of the primal SDP as a generalized form of branching in quantum computation. (This is joint work with Mike Saks and Mario Szegedy.) Matthias Christandl: A new generic proof for the security of quantum key distribution We present a new proof for the security of quantum key distribution. The presented proof is general in nature and applies to prepare-and-measure protocols such as BB84 as well as entanglement-based quantum cryptography such as E91. We use techniques that do not relate to entanglement distillation and thus differ significantly from all known security proofs. In order to derive a general security threshold we apply the recent result on privacy amplification in the presence of a quantum mechanical adversary by König, Maurer and Renner (2003). (This is joint work with Artur Ekert and Renato Renner.) Christoph Durr: Quantum query complexity of some graph problems Quantum algorithms for graph problems are considered, both in the adjacency matrix query model and in an adjacency list-like array model. We give almost tight lower and upper bounds for Connectivity, Strong Connectivity, Minimum Spanning Tree and Single Source Shortest Paths. (This is joint work with Mark Heiligman, Peter Hoyer, Mehdi Mhalla, and Yahui Lei.) Ivette Fuentes-Guridi: Holonomic quantum computation in the presence of decoherence We investigate the effects of decoherence in the geometric evolution of states of a degenerate quantum system. This is done by generalizing the scheme for geometric phases in open systems to non-Abelian holonomies. The formalism is applied to estimate the errors produced by performing an universal set of holonomic quantum gates in the presence of an environment. We pinpoint the single source of error in the scheme that must be corrected to achieve holonomic quantum computation completely robust to decoherence. Aram Harrow: Coherent communication of classical messages I define coherent communication in terms of a simple primitive, show it is equivalent to the ability to send a classical message with a unitary or isometric operation, and use it to relate other resources in quantum information theory. Using coherent communication, I can generalize super-dense coding to prepare arbitrary quantum states instead of only classical messages. I also derive single-letter formulae for the classical and quantum capacities of a bipartite unitary gate assisted by an arbitrary fixed amount of entanglement per use. Louis Kauffman: Braiding operators and quantum computing This talk will prove that there is a universal set of gates for quantum computing consisting in A single unitary solution R to the Yang-Baxter equation. Local unitary single qubit operations. The matrix R is the change of basis matrix taking the standard basis of a 2-qubit vector space to the Bell basis. This matrix is not only a unitary solution to the Yang-Baxter equation, it also gives rise to an interesting invariant of knots and links. This talk will pivot on this Theorem and discuss relationships between braids, knots, topological and quantum entanglement and quantum computing. From the point of view of this Theorem, any quantum computer can be configured as representation of an element in a generalization of the Artin Braid group. (This is joint work with Sam Lomonaco.) Sophie Laplante: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments We prove a very general lower bound technique for quantum and randomized query complexity that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted, unweighted methods of Ambainis, and the spectral method of Barnum, Saks, and Szegedy. As an immediate consequence of our main theorem, adversary methods can only prove lower bounds for Boolean functions f in O(min(sqrt{n C0(f)}, sqrt{n C1(f)})), where C0, C1 is the certificate complexity, and n is the size of the input. We also derive a general form of the ad hoc weighted method used by Hoyer, Neerbek, and Shi to give a quantum lower bound on ordered search and sorting. Reference: quant-ph/0311189 (This is joint work with Frederic Magniez.) David Poulin: Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect We present an efficient quantum algorithm to measure the average fidelity decay of a quantum map under perturbation using a single bit of quantum information. Our algorithm scales only as the complexity of the map under investigation, so for those maps admitting an efficient gate decomposition, it provides an exponential speed-up over known classical procedures. Fidelity decay is important in the study of complex dynamical systems, where it is conjectured to be a signature of quantum chaos. Our result also illustrates the role of chaos in the process of decoherence. Barry Sanders: Sharing secret quantum states: theory and experiment Threshold quantum secret sharing enables a quantum state to be transmitted to multiple players who cannot be trusted, whereas certain groups of players can be trusted. Quantum secrets may need to be shared for distributed quantum computing protocols, for quantum communication where trust is an issue, and for distributing quantum money, for example. I explain threshold quantum secret sharing, discuss continuous variable threshold quantum secret sharing, and present results of a recent successful threshold quantum secret sharing experiment implemented in a continuous variable system. Daniel Terno: Quantum information and special relativity Relativistic effects affect nearly all notions of quantum information theory. The vacuum behaves as a noisy channel, even if the detectors are perfect. The standard definition of a reduced density matrix fails for photon polarization because the transversality condition behaves like a superselection rule. We can, however, define an effective reduced density matrix which corresponds to a restricted class of positive operator-valued measures. There are no pure photon qubits, and no exactly orthogonal qubit states. Reduced density matrices for the spin of massive particles are well-defined, but are not covariant under Lorentz transformations. The spin entropy is not a relativistic scalar and has no invariant meaning. The distinguishability of quantum signals and their entanglement depend on the relative motion of observers. Posters Charlene Ahn Quantum error correction for continuously detected errors Muhammed Sabieh Anwar Preparing pure initial states from para-hydrogen Anne Braodbent Multi-party pseudo-telepathy Hilary Carteret Exact asymptotics for the quantum walk on the line Circuits for the direct detection of entanglement without the addition of noise Kai Chen A matrix realignment method for recognizing entanglement Donny Cheung Improved bounds for approximate quantum Fourier transforms Sora Choi Quantum key distribution network between various groups Igor Devatek Triple trade-offs in quantum Shannon theory Leonid Fedichkin Additivity of decoherence measures for multiqubit quantum systems Stephen Fenner Implementing the fanout gate by a Hamiltonian The power of constant-depth quantum circuits Fanout is hard to implement in constant with generalized Toffoli gates Jose Fernandez Quantum circuits for discrete logarithms on Galois Fields Theoretical methods and experimental implementations of non-adiabatic (heat bath) algorithmic cooling Ivette Fuentes-Guridi Holonomic quantum computation in the presence of decoherence Jim Harrington Local rules for protecting topological quantum memory Lawrence Ioannou Detecting entanglement with partial information Kazuo Iwama Quantum oracle computation with and without noises Phil Kaye Efficient implementation of quantum discrete logarithm algorithms on elliptic curves over extensions of GF(2) Viv Kendon Entanglement in Shor's algorithm Avanti Ketkar & Santosh Kumar Bounds on stabilizer codes over GF(q 2 ) Andreas Klappenecker Mutually unbiased bases Takeshi Koshiba Characterizing the existence of quantum one-way permutations Jozef Kosik Scattering model of quantum random walk Vasilijs Kravcevs Boolean function computation by probabilistic and quantum decision trees Maksim Kravtsev Models of probabilistic reversible automata and quantum counterparts Keiji Matsumoto Additivity of Holevo capacity and strong converse of channel capacity and entanglement dilution Carlos Mochon Computing with anyons Masoud Mohseni Optical realization of optimal unambiguous discrimination for pure and mixed quantum states Mio Murao LOCC extraction of distributed quantum information Falk Niehoerster & Helge Rose The Fraunhofer Quantum Computing Services - A parallel simulator of quantum computing processes Harold Ollivier Quantum convolutional coding Tobias Osborne The propagation of quantum information through a spin system Michel Pioro-Ladriere Electron Spin based qubits in lateral gated quantum dots Sergio de Rinaldis Distinguishability of complete and unextendible product bases David Roberts Non-local correlations as information theoretic resources Jeremie Roland Robustness to noise of Hamiltonian search algorithms David Santos Optimal strategies in quantum message authentication Toshiyuki Shimono Numerical test of superadditivity of entanglement of formation for four-qubit states Marcus Silva Erasure thresholds for efficient linear optics quantum computing Graeme Smith Efficient multiparty quantum data hiding Won Min Son D-outcome measurement for a nonlocality test Rob Spekkens The cryptographic power of private shared reference frames Krysta Svore Compiling quantum computations into elementary operations Christino Tamon A note on graphs resistant to quantum uniform mixing Yuuki Tokunaga Anonymous quantum cash Ben Toner Quantifying and generalizing the Kochen-Specker theorem Nicholas Whitlock A theory for matter-wave detection | invited | — | 50 | Debbie Leung | — |
| Exponential separation of quantum and classical one-way communication complexity | invited | — | 50 | Iordanis Kerenidis | — |
| From entanglement to secret key and back | invited | — | 50 | Andreas Winter | — |
Contributed Talks |
|||||
| Quantum Computation in Groups | invited | — | 50 | Alex Russell | — |
| Stronger Error Reduction for QMA | invited | — | 50 | John Watrous | — |
| Additivity questions in quantum information theory There are a number of interesting, open additivity questions in quantum information theory. Recently, I have been able to show that some of these are equivalent. I will discuss open additivity questions in general and this proof of equivalence in particular. Kiyoshi Tamaki: Unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel We prove the unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel. We assume that Alice has an ideal single photon source and Bob has detectors that discriminate between single photon states on one hand and vacuum state or multiphoton states on the other hand. We use a reduction to an entanglement distillation protocol initiated by a local filtering process in our proof. The bit errors and the phase errors are correlated after the filtering, and we can bound the amount of phase errors from the observed bit errors by an estimation method involving nonorthogonal measurements. Leslie Valiant: Holographic Algorithms John Watrous: Stronger Error Reduction for QMA The complexity class QMA is a bounded-error quantum computational variant of the class NP, where a quantum state plays the role of a certificate. It is known that the error of a given QMA protocol can be reduced exponentially at the cost of a polynomial increase in the length of the certificate. In this talk, I will prove that such a reduction in error is in fact possible with no increase in the length of the certificate whatsoever. Applications of this fact include a proof that logarithmic-length quantum certificates give no increase in power over BQP and a simple proof that QMA is contained in the class PP. Andreas Winter: From entanglement to secret key and back The last year has seen a series of dramatic progresses in the areas of quantum channel capacities, entanglement distillation and our understanding of how these problems relate to secret communication. In this talk I will first review the analogy between the theories of entanglement and key distillation. Then I go on to explain the elements of the recent progress, first describing Devetak's recent reduction of quantum state transmission to private communication and our subsequent joint work generalising this to entanglement/secret key distillation. These findings put into a new light the earlier observations (by Acin et al.and Bruss et al.) of qualitative equivalence between these two tasks, and also prepared the ground for the recent step forward by Horodecki et al., to formulate key distillation strictly within the LOCC paradigm and then to exhibit bound entangled states which nevertheless contain secret key. Contributed Talks Howard Barnum: Query complexity & semidefinite programming We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we do the following: We show that as far as query complexity is concerned, the workspace of a quantum computer used to evaluate f(x) by querying the bits of an n-bit string x can be limited to n + k, where f takes k bit strings as values. We give an algorithm that on input the truth table of a partial boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm that attempts to evaluate f in t queries. We use semidefinite programming duality to formulate a dual SDP Phat(f, t, e) that is feasible if and only if f cannot be avluated within error e by a t-step quantum query algorithm. Using this SDP we derive a general lower bound for query complexity that encompasses a lower bound method of Ambainis and its generalizations. We give an interpretation of the primal SDP as a generalized form of branching in quantum computation. (This is joint work with Mike Saks and Mario Szegedy.) Matthias Christandl: A new generic proof for the security of quantum key distribution We present a new proof for the security of quantum key distribution. The presented proof is general in nature and applies to prepare-and-measure protocols such as BB84 as well as entanglement-based quantum cryptography such as E91. We use techniques that do not relate to entanglement distillation and thus differ significantly from all known security proofs. In order to derive a general security threshold we apply the recent result on privacy amplification in the presence of a quantum mechanical adversary by König, Maurer and Renner (2003). (This is joint work with Artur Ekert and Renato Renner.) Christoph Durr: Quantum query complexity of some graph problems Quantum algorithms for graph problems are considered, both in the adjacency matrix query model and in an adjacency list-like array model. We give almost tight lower and upper bounds for Connectivity, Strong Connectivity, Minimum Spanning Tree and Single Source Shortest Paths. (This is joint work with Mark Heiligman, Peter Hoyer, Mehdi Mhalla, and Yahui Lei.) Ivette Fuentes-Guridi: Holonomic quantum computation in the presence of decoherence We investigate the effects of decoherence in the geometric evolution of states of a degenerate quantum system. This is done by generalizing the scheme for geometric phases in open systems to non-Abelian holonomies. The formalism is applied to estimate the errors produced by performing an universal set of holonomic quantum gates in the presence of an environment. We pinpoint the single source of error in the scheme that must be corrected to achieve holonomic quantum computation completely robust to decoherence. Aram Harrow: Coherent communication of classical messages I define coherent communication in terms of a simple primitive, show it is equivalent to the ability to send a classical message with a unitary or isometric operation, and use it to relate other resources in quantum information theory. Using coherent communication, I can generalize super-dense coding to prepare arbitrary quantum states instead of only classical messages. I also derive single-letter formulae for the classical and quantum capacities of a bipartite unitary gate assisted by an arbitrary fixed amount of entanglement per use. Louis Kauffman: Braiding operators and quantum computing This talk will prove that there is a universal set of gates for quantum computing consisting in A single unitary solution R to the Yang-Baxter equation. Local unitary single qubit operations. The matrix R is the change of basis matrix taking the standard basis of a 2-qubit vector space to the Bell basis. This matrix is not only a unitary solution to the Yang-Baxter equation, it also gives rise to an interesting invariant of knots and links. This talk will pivot on this Theorem and discuss relationships between braids, knots, topological and quantum entanglement and quantum computing. From the point of view of this Theorem, any quantum computer can be configured as representation of an element in a generalization of the Artin Braid group. (This is joint work with Sam Lomonaco.) Sophie Laplante: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments We prove a very general lower bound technique for quantum and randomized query complexity that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted, unweighted methods of Ambainis, and the spectral method of Barnum, Saks, and Szegedy. As an immediate consequence of our main theorem, adversary methods can only prove lower bounds for Boolean functions f in O(min(sqrt{n C0(f)}, sqrt{n C1(f)})), where C0, C1 is the certificate complexity, and n is the size of the input. We also derive a general form of the ad hoc weighted method used by Hoyer, Neerbek, and Shi to give a quantum lower bound on ordered search and sorting. Reference: quant-ph/0311189 (This is joint work with Frederic Magniez.) David Poulin: Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect We present an efficient quantum algorithm to measure the average fidelity decay of a quantum map under perturbation using a single bit of quantum information. Our algorithm scales only as the complexity of the map under investigation, so for those maps admitting an efficient gate decomposition, it provides an exponential speed-up over known classical procedures. Fidelity decay is important in the study of complex dynamical systems, where it is conjectured to be a signature of quantum chaos. Our result also illustrates the role of chaos in the process of decoherence. Barry Sanders: Sharing secret quantum states: theory and experiment Threshold quantum secret sharing enables a quantum state to be transmitted to multiple players who cannot be trusted, whereas certain groups of players can be trusted. Quantum secrets may need to be shared for distributed quantum computing protocols, for quantum communication where trust is an issue, and for distributing quantum money, for example. I explain threshold quantum secret sharing, discuss continuous variable threshold quantum secret sharing, and present results of a recent successful threshold quantum secret sharing experiment implemented in a continuous variable system. Daniel Terno: Quantum information and special relativity Relativistic effects affect nearly all notions of quantum information theory. The vacuum behaves as a noisy channel, even if the detectors are perfect. The standard definition of a reduced density matrix fails for photon polarization because the transversality condition behaves like a superselection rule. We can, however, define an effective reduced density matrix which corresponds to a restricted class of positive operator-valued measures. There are no pure photon qubits, and no exactly orthogonal qubit states. Reduced density matrices for the spin of massive particles are well-defined, but are not covariant under Lorentz transformations. The spin entropy is not a relativistic scalar and has no invariant meaning. The distinguishability of quantum signals and their entanglement depend on the relative motion of observers. Posters Charlene Ahn Quantum error correction for continuously detected errors Muhammed Sabieh Anwar Preparing pure initial states from para-hydrogen Anne Braodbent Multi-party pseudo-telepathy Hilary Carteret Exact asymptotics for the quantum walk on the line Circuits for the direct detection of entanglement without the addition of noise Kai Chen A matrix realignment method for recognizing entanglement Donny Cheung Improved bounds for approximate quantum Fourier transforms Sora Choi Quantum key distribution network between various groups Igor Devatek Triple trade-offs in quantum Shannon theory Leonid Fedichkin Additivity of decoherence measures for multiqubit quantum systems Stephen Fenner Implementing the fanout gate by a Hamiltonian The power of constant-depth quantum circuits Fanout is hard to implement in constant with generalized Toffoli gates Jose Fernandez Quantum circuits for discrete logarithms on Galois Fields Theoretical methods and experimental implementations of non-adiabatic (heat bath) algorithmic cooling Ivette Fuentes-Guridi Holonomic quantum computation in the presence of decoherence Jim Harrington Local rules for protecting topological quantum memory Lawrence Ioannou Detecting entanglement with partial information Kazuo Iwama Quantum oracle computation with and without noises Phil Kaye Efficient implementation of quantum discrete logarithm algorithms on elliptic curves over extensions of GF(2) Viv Kendon Entanglement in Shor's algorithm Avanti Ketkar & Santosh Kumar Bounds on stabilizer codes over GF(q 2 ) Andreas Klappenecker Mutually unbiased bases Takeshi Koshiba Characterizing the existence of quantum one-way permutations Jozef Kosik Scattering model of quantum random walk Vasilijs Kravcevs Boolean function computation by probabilistic and quantum decision trees Maksim Kravtsev Models of probabilistic reversible automata and quantum counterparts Keiji Matsumoto Additivity of Holevo capacity and strong converse of channel capacity and entanglement dilution Carlos Mochon Computing with anyons Masoud Mohseni Optical realization of optimal unambiguous discrimination for pure and mixed quantum states Mio Murao LOCC extraction of distributed quantum information Falk Niehoerster & Helge Rose The Fraunhofer Quantum Computing Services - A parallel simulator of quantum computing processes Harold Ollivier Quantum convolutional coding Tobias Osborne The propagation of quantum information through a spin system Michel Pioro-Ladriere Electron Spin based qubits in lateral gated quantum dots Sergio de Rinaldis Distinguishability of complete and unextendible product bases David Roberts Non-local correlations as information theoretic resources Jeremie Roland Robustness to noise of Hamiltonian search algorithms David Santos Optimal strategies in quantum message authentication Toshiyuki Shimono Numerical test of superadditivity of entanglement of formation for four-qubit states Marcus Silva Erasure thresholds for efficient linear optics quantum computing Graeme Smith Efficient multiparty quantum data hiding Won Min Son D-outcome measurement for a nonlocality test Rob Spekkens The cryptographic power of private shared reference frames Krysta Svore Compiling quantum computations into elementary operations Christino Tamon A note on graphs resistant to quantum uniform mixing Yuuki Tokunaga Anonymous quantum cash Ben Toner Quantifying and generalizing the Kochen-Specker theorem Nicholas Whitlock A theory for matter-wave detection | invited | — | 50 | Peter Shor | — |
| On the Universality of Adiabatic Quantum Computation | invited | — | 50 | Dorit Aharonov | — |
| Physical limits of heat-bath algorithmic cooling | invited | — | 50 | Leonard Schulman | — |
| Tradeoffs between the communication complexity and the number of storage qubits | invited | — | 50 | Hartmut Klauck | — |
| Unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel | invited | — | 50 | Kiyoshi Tamaki | — |
Committees
OC
| Name | Position | Role | Affiliation |
|---|---|---|---|
| Ashwin Nayak | member | — | IQC and PI |
| Daniel Gottesman | member | — | Perimeter Institute, Waterloo |
| Michele Mosca | member | — | University of Waterloo and Perimeter Institute, Waterloo |
SC
| Name | Position | Role | Affiliation |
|---|---|---|---|
| Charles H. Bennett | member | — | IBM |
| Daniel Gottesman | member | — | Perimeter Institute, Waterloo |
| David DiVincenzo | member | — | IBM |
| Harry Buhrman | member | — | CWI, Amsterdam |
| Isaac Chuang | member | — | MIT, Cambridge |
| John Watrous | member | — | University of Waterloo |
| Miklos Santha | member | — | CNRS LRI, Orsay |
| Umesh Vazirani | member | — | UC Berkeley |
Local
| Name | Position | Role | Affiliation |
|---|---|---|---|
| Greg Brennan | chair | — | — |
| Aziz Kara | member | — | — |
| Colleen Brickman | member | — | — |
| David Poulin | member | — | — |
| Fiona McAlister | member | — | — |
| Howard Burton | member | — | — |
| Ivette Fuentes-Guridi | member | — | — |
| John McCormick | member | — | — |
| Karen Wiatowski | member | — | — |
| Kari Cox | member | — | — |
| Lena Yost | member | — | — |
| Martin Roetteler | member | — | — |
| Phillip Kaye | member | — | — |
| Rita Schwander | member | — | — |
| Sue Scanlan | member | — | — |
| Wendy Reibel | member | — | — |