QIP · 2004

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.)

The late Rolf Landauer has once claimed that "information is physical". The main point of this talk is to argue that "physics is informational"! At the moment, quantum information theory is replete with beautiful theorems on what is and is not possible according to quantum mechanics. For example, quantum key distribution is possible but quantum bit commitment is not. But the axioms of quantum mechanics are strange and ad hoc, reflecting at best the history that led to discovering this new world order. It's time to pause and reflect on what is really fundamental and what are merely consequences. Could information be the answer? (This is joint work with Christopher Fuchs)

I will present two new quantum algorithms based on quantum walks: - an O(N^{2/3}) query algorithm for element distinctness (the problem of finding two equal elements among N given elements). - an O(N^{1/2}\log N) step quantum algorithm for finding a marked item on 2-dimensional grid. Both algorithms are based on the same general technique. I will also describe this technique and show how to decompose it into a sequence of steps which can then be applied to other problems. The second algorithm is joint work with Julia Kempe, Alexander Rivosh and Neil Shenvi.

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.

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.

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.

Several researchers, including Leonid Levin, Gerard 't Hooft, and Stephen Wolfram, have argued that quantum mechanics will break down before the factoring of large numbers becomes possible. If this is true, then there should be a natural "Sure/Shor separator" -- that is, a set of quantum states that can account for all experiments performed to date, but not for Shor's factoring algorithm. We propose as a candidate the set of states expressible by a polynomial number of additions and tensor products. Using a recent lower bound on multilinear formula size due to Raz, we then show that states arising in quantum error-correction require n^{Omega(log n)} additions and tensor products even to approximate, which incidentally yields the first superpolynomial gap between general and multilinear formula size of functions. More broadly, we introduce a complexity classification of pure quantum states, and prove many basic facts about this classification. Our goal is to refine vague ideas about a breakdown of quantum mechanics into specific hypotheses that might be experimentally testable in the near future. "Bonus features" will be included for those who have already heard this talk.

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.

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

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.

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.

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.)

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.)

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.

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.)

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.)

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.

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.

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.

We investigate various aspects of the nonlocal effects that can occur when entangled quantum information is shared between two parties. We explain how these effects can significantly affect the soundness of two-prover interactive proof systems--which raises new questions about the expressive power of these systems. We then embark on a program to establish bounds on what nonlocal effects can do. These bounds can be regarded as generalizations of the so-called Tsirelson inequality. We also consider the amount of entanglement required to achieve optimal nonlocal effects. This is joint work with Peter Hoyer, Ben Toner, and John Watrous.

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem and prove that its quantum one-way communication complexity is O(log n), yet any randomized one-way protocol with bounded error must use Omega(sqrt{n}) bits of communication. No asymptotic gap for one-way communication was previously known.

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.

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.

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.

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.

The model of adiabatic computation with local Hamiltonians has recently attracted considerable attention. Its computational power was unclear. I will present a recent result with van-Dam, Kempe, Landau, Lloyd and Regev which settles this question, in which we show that adiabatic computation with local Hamiltonians is as powerful as conventional quantum computation. This holds even in the physically realistic setting in which the adiabatic system is set on a two dimensional grid with nearest neighbor interactions. Apart from presenting the result, I will also discuss its possible implications, mainly for quantum algorithms design.

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.