Quantum Computation and Information Seminar 

In this talk some recent developments on entanglement theory will be addressed. A simple strategy of entanglement estimation, given by a lower bound on the Generalized Robustness of Entanglement will be explained. A second topic will be entanglement extraction. We will dicuss how to get entanglement from a degenerate Fermi gas, and also describe two distinct experimental proposals, one with ultra-cold neutrons, other with semi-conductors. Finally, the problem of Entanglement Transfer from a pair of qubits to another pair will be described with the exhibition of some recent results.

Conclusion of the previous talk.

Based on the exogenous semantics approach to enriching logics, previously used to develop the exogenous propositional quantum logic, a novel exogenous quantum first-order logic (EQFOL) is presented. Predicates are used to represent families of quantum bits. A quantum interpretation structure includes a superposition of classical valuations according to the principles of the exogenous semantics approach. But, a pointed variation is needed to cope with a modality introduced for stating properties of omitting symbols. An axiomatization is proposed. Some examples are provided. Finally, the envisaged completeness result is discussed. Joint work with Jaime Ramos, Paulo Mateus and Mingsheng Ying.

Joint session with LC Seminar.

Secret sharing and secure multiparty computation (also called "secure function evaluation") are fundamental primitives in modern cryptography, allowing a group of mutually distrustful players to perform correct, distributed computations under the sole assumption that some number of them will follow the protocol honestly. This paper investigates how much trust is necessary - that is, how many players must remain honest - in order for distributed quantum computations to be possible. We present a verifiable quantum secret sharing (VQSS) protocol, and a general secure multiparty quantum computation (MPQC) protocol, which can tolerate any (n-1)/2 cheaters among n players. Previous protocols for these tasks tolerated (n-1)/4 and (n-1)/6 cheaters, respectively. The threshold we achieve is tight - even in the classical case, "fair" multiparty computation is not possible if any set of n/2 players can cheat. Our protocols rely on approximate quantum error-correcting codes, which can tolerate a larger fraction of errors than traditional, exact codes. We introduce new families of authentication schemes and approximate codes tailored to the needs of our protocols, as well as new state purification techniques along the lines of those used in fault-tolerant quantum circuits. Joint work with Claude Crepeau, Daniel Gottesman, Avinatan Hassidim and Adam Smith.

Dagger compact closed categories were recently introduced by Abramsky and Coecke (under the name "strongly compact closed categories") as an abstract presentation of the category of Hilbert spaces and linear maps. I subsequently showed that completely positive maps could be explained as a purely categorical construction in Abramsky and Coecke's framework, via the so-called CPM construction. In this talk, I will recall the definitions of these categories and their graphical languages, and discuss some useful constructions on them.

Conclusion of the previous talk.

It has been recently pointed that, for certain classes of states, quantum entanglement enhances the "speed" of evolution of composite quantum systems, as measured by the time a given initial state requires to evolve to an orthogonal state. We provide a systematic study of this effect for pure states of bipartite systems of low dimensionality, considering both distinguishable (two-qubits) subsystems, and systems constituted of two indistinguishable particles. Mixed states are also considered. Finally, we discuss the entropic separability criterion and the so-called maximally entangled mixed states (MEMS).

The aim of the seminar is to give an introduction to topological quantum computation. We start by explaining how two logical qubits can be encoded in a torus due to degenerate physical qubits configurations. The physical stability of such systems are the main motivation for its use in quantum computation, this issue is related to error detection and correction at physical level. Possible gates and state measurement can be implemented trough the use of anyons and vortexes and the respective braiding. We also give a brief overview of topological and conformal field theories and discuss the possibility of its use for quantum computation.

The zero-error capacity of a classical discrete communication channel was first defined by Shannon as the least upper bound of rates for which is possible to send encoded information with zero probability of error. This kind of capacity differs from the "ordinary" capacity that requires only asymptotically small error probability. We extend the concept of zero-error capacity for a noisy quantum channel and discuss its main properties. Connections with the theory of quantum noiseless subsystems are established.

We present a characterization of quantum phase transitions in terms of the the overlap function between two ground states obtained for two different values of external parameters. On the examples of the Dicke and $\mathrm{XY}$ models, we show that the regions of criticality of a system are marked by the extremal points of the overlap and functions closely related to it. Further, we discuss the connections between this approach and the Anderson orthogonality catastrophe as well as its connection with the dynamical study of the Loschmidt echo for critical systems. Joint work with Paolo Zanardi.

Trapped ions have been a very important resource for the experimental study of quantum information and are a promising technology for the construction of a quantum computer. In this talk, we focus on the description of the physical implementation of quantum computing using cold trapped ions, give concrete examples of the used gates, discuss their limitations and present current trends to improve on decoherence and scalability.

The work of Ludwig Boltzmann, the founder of modern atomism and of statistical reasoning in physics, is reviewed and analyzed, in the context of his time, its implications and some modern developments. (Invited talk of the Colloquium "O Legado de Boltzmann", organized by the Department of Physics of Faculdade de Engenharia da Universidade do Porto).

The description of many-body quantum states is, typically, very hard. The reason is that the number of parameters needed to characterize the quantum state of $N$ $d$-level systems scales as $d^N$, so that even for qubits ( $d=2$) already for $N>40$ it is impossible to store all the corresponding coefficients. Furthermore, if one wants to determine the expectation value of any observable one needs to perform a number of basic operations which also scale exponentially with the number of particles. However, in Nature, only some particular states appear, and thus it may happen that different ways of parametrizing quantum states are much more efficient and do not require an exponential scaling. In this talk I presented a new characterization of quantum states, what we call Projected Entangled-Pair States (PEPS). This characterization is based on constructing pairs of maximally entangled states in a Hilbert space of dimension $D^2$, and then projecting those states in subspaces of dimension $d$. In one dimension, one recovers the familiar matrix product states, whereas in higher dimensions this procedure gives rise to other interesting states. We have used this new parametrization to construct numerical algorithms to simulate the ground state properties and dynamics of certain quantum-many body systems in two dimensions. The results are very encouraging, since we have been able to simulate $20\times 20$ spin $1/2$ lattices interacting with the Heisenberg nearest neighbor Hamiltonian, as well as with other frustrated Hamiltonians.

Adiabatic Quantum Computation has been proposed in 2001 by Farhi et al. as an alternative way to perform quantum computation. The protocol consists in passing from a initial Hamiltonian with a well known and easy to prepare ground state to the ground state of a final Hamiltonian (or problem Hamiltonian) which encodes the answer to a given problem. The time taken to perform the computation is such that the adiabatic theorem applies, with a small enough probability of passing to an exited state remains limited: $T\sim {\Delta }_{\min }^{-2}$, where $T$ is the total computational time and ${\Delta }_{\min }$ is the minimum value of the energy difference between the ground and the first exited states taken along the evolution. Therefore the time scaling with $n$ will be mainly determined by the behavior of the energy gap between the two lowest energy states. In this seminar we will introduce the Adiabatic Model of Computation and present a simple model that, due to its symmetry, permits to give analytic results and see how the gap scales depending of few characteristics of the computational problem.

Quantum computers are likely to be much more vulnerable to noise than classical computers, so it is likely they will need to be encoded using quantum error-correcting codes and computations will be performed using fault-tolerant protocols. One critical result states that there is a threshold error rate, such that arbitrarily long reliable computations are possible if the error rate per gate and time step in the computer are below the threshold. I will give an overview of some recent work on the threshold, with a slight emphasis on recent work by Aliferis, Preskill, and myself. We gave a new proof of the threshold which is simpler and more general than previous proofs, and proved a higher value of the threshold error rate. We also showed that a threshold exists with more general non-Markovian environments than was previously known.

Quantum Walks (QWs) are devised as an important ingredient of quantum computation. Several physical systems have been proposed to implement them. I will discuss a non-linear QW which gives rise to interesting phenomena, including the formation of soliton structures. Depending on the strength of the non-linearity, one finds different regimes for the behavior of the solitons. The region with large values of the strength parameter shows a chaotic dependence.

The problem of distinguishing different combinatorial objects represented by cospectral matrices appears in many diverse mathematical contexts and it has large application in pattern recognition. The problem is related to the traditional question "can we hear the shape of a drum?". In this talk I will give evidence that representing graphs by certain unitary matrices provides a finer sieve in distinguishing nonisomorphic graph which are cospectral with respect to the usual representations, like the adjacency matrix or the laplacian. The matrices considered can be seen as inducing the coherent diffusion of a quantum particle in the graph taken into analysis. Such a quantum evolution depends on the graph. I will show that for certain graphs the quantum evolution helps in distinguishing isomorphism classes. The talk is based on the paper "David Emms, Edwin R. Hancock, Simone Severini and Richard C. Wilson, A Matrix Representation of Graphs and its Spectrum as a Graph Invariant, The Electronic Journal of Combinatorics, 13 (2006), #R34. This is available on the web at the address www.combinatorics.org/Volume_13/PDF/v13i1r34.pdf or www-users.york.ac.uk/~ss54.

In this talk, I shall briefly describe the scenario of quantum entanglement transformation, and then adress the following problems: the existence of entanglement catalysis; when catalysis is useful for probabilistic entanglement transformation; asymptotical equivalence of catalyst and multi-copy transformation; partial recovery of quantum entanglement.

In quantum Shannon theory, the calculational task for any given quantum channel is to find a set of quantum states that are maximally resistant to distortion by the channel. In quantum cryptography, however, one welcomes the circumstance that quantum states are sensitive to their environments; for it is a feature that can be used to detect eavesdropping. When an eavesdropper gathers information on the identity of one of a set of nonorthogonal states, she necessarily causes a disturbance to those states. This situation calls for a means to quantify how sensitive to eavesdropping one alphabet of quantum states is over another. We explore one such measure, and use it to define a set of maximally sensitive quantum states. Sets of such maximally sensitive quantum states have several interesting properties that indicate they may be of wider interest than the problem from which they came.

We demonstrate that quantum entanglement can help separated individuals in making decisions if their goal is to find each other in the absence of any communication between them. We derive a Bell-like inequality that the efficiency of every classical solution for our problem has to obey, and demonstrate its violation by the quantum efficiency. This proves that no classical strategy can be more efficient than the quantum one.