Quantum Computation and Information Seminar 

Randomization of quantum states is the quantum analogue of the classical one-time pad. Hayden, Leung, Shor, and Winter (2004) showed that for randomizing an arbitrary $d$-dimensional quantum state to a state close to the completely mixed state, a set of $O(d\hspace{0.5em}\log d/{ϵ}^2)$ unitary operations suffice. This relaxed scheme cuts approximately by a factor of 2, the number of key bits required for perfect randomization. Soon after, Ambainis and Smith (2004) gave explicit constructions of such sets. We will present an improved efficient construction of an approximately randomizing map that uses $O(d/{ϵ}^2)$ Pauli operators. Then, we will show that a random set with $O((d/{ϵ}^2)\log (1/ϵ))$ unitaries chosen from a suitable set randomize $d$-dimensional states to within $ϵ$ in trace distance with high probability. This is joint work with Paul Dickinson.

Shannon in celebrated works had shown that $n$ bits of shared key is necessary and sufficient to transmit $n$-bit classical information in an information-theoretically secure way. Ambainis, Mosca, Tapp and de Wolf [FOCS 2000, quant-ph/0003101] considered a more general setting, referred to as Private quantum channels, in which instead of classical information, quantum states are required to be transmitted and only one-way communication is allowed. They show that in this case $2n$ bits of shared key is necessary and sufficient to transmit an n-qubit state. We consider the most general setting in which we allow for all possible combinations i.e. we let the input to be transmitted, the message sent and the shared resources to be classical/quantum. We develop a general framework by which we are able to show tight bounds on communication/shared resources in all but one of these cases and this includes the results of Shannon and Ambainis et al.

Quantum computing skeptics have claimed that any theory involving exponentially-long vectors is inherently unreasonable. But if someone hands you a quantum state, is that really like being handed an exponential amount of classical information? I will describe recent results suggesting that the answer, at least for complexity-theoretic purposes, is "no". These results include simulations of quantum advice using classical advice, and a conditional "dequantization" of John Watrous' quantum proof protocol for the Group Non-Membership problem. Based partly on joint work with Greg Kuperberg.

I will start by introducing a scheme for quantum communication using an unmodulated and unmeasured spin chain. It presents an alternative to converting between static and flying qubits in order to connect up distinct quantum processors. I present some approaches to accomplish perfect quantum communication through a spin chain despite the dispersion of quantum information in the chain. I also discuss the accomplishment of gates between distant spins thorough a spin chain. Apart from transfer, a chain can also be used to simultaneously generate and distribute a maximally entangled state between distant sites, as I illustrate through a chain of coupled qutrits.

Quantum mechanics is one of the best confirmed theories of nature. Still - in contrast to all other theories - it requires an interpretation and it exhibits features which seem to contradict common sense and even classical logic. It is sometimes argued that quantum physics applies to the microcosmos while classical physics holds in our macroworld. We will discuss experiments which try to approach the mesoscopic and macroscopic world from below - studying matter wave interference with particles of increasing size and complexity. The experiments also show that quantum physics itself is an important key to the classical appearance of our everyday world - as entanglement with the environment destroys the isolation of the individual quantum systems and renders the particula quantum features unobservable. Although the present research on molecule interferometry is focused on illucidating fundamental issues of quantum physics we also identify several applied research directions using molecular matter waves.

Conclusion of the previous talk.

A brief tutorial on quantum complexity classes is given. The relationship between quantum Turing machines, quantum circuits and the query complexity model is described from a complexity theoretical point of view. Open questions and problems in the area are outlined.

A brief overview on classical algorithms for the match-count problem is given. A quantum algorithm for finding the maximum match-count between two strings is presented. The expected run time of the proposed algorithm for strings of size n is shown to be $O(n)$, which is a lower bound for the problem at hand. Joint ongoing work with P. Mateus.

A quantum attack to a class of classical zero-knowledge protocols is presented. The attack provides an evidence to a third party that the prover has interacted with the verifier. An important corollary of this attack is that proof transferabilty for classical zero-knowledge protocols is possible when the verifier has access to quantum information. Joint work with C. Crépeau, K. Ekert and Y. Omar.

In the last decades the Monte Carlo method (MC) has proved to be a powerful tool for the investigation of transport properties of charge carriers in semiconductors in high electric fields (typically of the order of kV/cm). In particular, MC simulations are useful for studying noise properties. These are relevant from the technologic point of view as well as for their ability to provide information on the physical behavior of “hot” carriers. However, up to now no effort was done (at least for bulk zinc-blend semiconductors) to perform this kind of study in the case of systems driven by crossed electric and magnetic fields. To this aim we consider bulk n-GaAs in the context of a three valleys model. $\Gamma$, L and X valleys are assumed spherical and nonparabolic. Electron scatterings due to ionized impurities, acoustic and polar optical phonons in each valley as well as intervalley transitions between the equivalent and nonequivalent valleys are accounted for. The time evolution of the electron wave-vector during free flights is treated by means of a local parabolic approximation of the dispersion law. Stochastic properties of electron transport are investigated by analyzing the electron velocity auto-correlation function and the spectral density of its fluctuations. These functions are shown to be significantly affected by the presence of the magnetic field. It is found that the spectrum of fluctuations exhibits interesting features such as signatures of nonparabolicity (implying a reduction of the expected cyclotron frequency) and nonlinearity (due to the different effective mass of valleys). For suitable electric field strengths, noise is lowered by the action of the magnetic field in a wide range of frequencies with a simultaneous decreasing of its total power.

We develop a notation for patterns of correlated measurements and local corrections together with a set of equations, which we call the measurement calculus. We show that patterns can be put in a standard form, where entanglement is done first, then measurement, then corrections. Various consequences are compositional proofs of universality for both the 1-qubit and the 2-qubit measurement based models, with robust and parsimonious generators, compositional embeddings between these models, and a proof that patterns without correlations may only implement Clifford operators. Joint work with V. Danos and P. Panangaden.

The status of the non-abelian hidden subgroup problems is one of the most fundamental open problems in quantum computation today. In particular, the graph automorphism problem may be formulated as hidden subgroup problem over the symmetric group $S_n$, and the shortest lattice vector problem as the hidden subgroup problem over the dihedral group $D_n$. It is natural to try to mimic the success of quantum algorithms for the abelian hidden subgroup problem (which include factoring and discrete log as special cases) for the non-abelian case. This involves Fourier transforms over nonabelian groups which are defined in terms of the irreducible complex representations of the group. In this talk I will describe what we have learnt about such algorithms in the last few years for both the dihedral and symmetric groups.

The relative weak coupling of neutral atoms to the environment makes them interesting candidates for the implementation of concepts of quantum information. We review several techniques to trap atoms in optical potentials, as optical lattices and microtraps, and discuss various schemes to implement quantum bits and gates. We furthermore describe an implementation of discrete time quantum walks in one dimension and on a two dimensional cartesian grids in such a system.

Entanglement is perhaps the most nonclassical of all quantum resources. It allows for otherwise impossible tasks, such as quantum teleportation. Nevertheless, entanglement by itself cannot be used to signal information between two parties or even reduce the number of classical bits that must be transmitted to communicate any given message between those parties. In apparent contradiction, there are distributed computational tasks that can be accomplished with exponentially less classical communication in the presence of entanglement, compared to the best possible all-classical protocol. Even more remarkably, there are distributed tasks that cannot be accomplished at all in a classical world when communication is not allowed, but that become possible if the non-communicating parties share prior entanglement. A real-life implementation of this phenomenon, known as pseudo-telepathy, would offer perhaps the most convincing evidence that we do not live in the kind of world that Einstein was dreaming to build. No previous knowledge of quantum mechanics will be assumed.

Quantum cryptographic systems are likely to become technologically important in the near future, and it is important to be confident of their correctness. Although several quantum protocols have been mathematically proved correct, we argue that further steps of verification are necessary in order to be confident of the correctness of a complete system, which is likely to combine both quantum and classical communication and computation. We have begun to apply formal modelling and verification techniques, which have been successful in the analysis of classical communication and cryptographic systems, to quantum systems; initially we have focussed on model-checking techniques, and in particular the probabilistic model-checking tool PRISM. This seminar will outline the challenges involved in formal verification of quantum systems, and report some initial results. This is joint work with Nick Papanikolaou and Raja Nagarajan of the University of Warwick, and is certainly work in progress.

The idea of generalizing the notion of Zero-Knowledge proof systems to the quantum scenario has long been investigated. Very few results were accomplished in the early years because such notions as "rewinding" don't work quantumly. This talk will explain the problems of early quantum zero-knowledge protocols and what recently made them finally possible in the quantum scenario. This talk is based on many results I contributed to in collaboration and a few recent papers of other authors.

We present a process algebra for specifying and reasoning about quantum security protocols. Since the computational power of the protocol agents must be restricted to quantum polynomial-time, we introduce the logarithmic cost quantum random access machine (QRAM), and incorporate it in the syntax of the algebra. Probabilistic transition systems give the semantic support for the process algebra. Term reduction is stochastic because quantum computation is probabilistic and, moreover, we consider a uniform scheduler to resolve non-deterministic choices. With the purpose of defining security properties, we also introduce observational equivalence and quantum computational indistinguishability, and show that the latter is a congruence relation. A simple corollary of this result asserts that any security property defined via emulation is compositional. Finally, we illustrate our approach by establishing the concept of quantum zero-knowledge protocol. Joint work with P. Adão.

Adiabatic quantum algorithms are a new approach to quantum computation. While being equivalent to standard quantum circuit model, they present a very different way of thinking about quantum algorithms. Adiabatic algorithms are based on the adiabatic theorem of quantum mechanics. Informally, the adiabatic theorem says that, when a Hamiltonian of a physical system is slowly transformed to a different Hamiltonian, the lowest energy state of the first Hamiltonian is transformed to the lowest energy state of the second Hamiltonian. In this talk, I will introduce the adiabatic approach and then present a new proof of quantum adiabatic theorem.

When the inputs of a function are distributed among remote parties, neither of them can determine its value as every party knows only her/his own data and not the data of the partners. To have an efficiency in computing the function higher than by a simple random guess the partners necessarily need to communicate. I will demonstrate the cases for which already a small amount of communication between the partners leads to the correct value of the function if they share quantum entanglement, while classically the same amount of communication leave them with an efficiency not better than by a random guess. Thus, although entanglement on its own cannot be used for communication (any such communication will also be a superluminal one!) it surprisingly can (significantly) save on communication. Such a reduction of communication complexity might be important in future for speeding up distributed computations, e.g. within VLSI circuits.