### Quantum Computing and Quantum Information Processing 2013

**Abstracts**

Michael Bremner (UTS)

**Towards a proof of the classical intractability of quantum simulation**

The information revolution is largely based on what a physicist would call a classical view of

information, assuming that it can be copied freely and is not disturbed by observation. Quantum

effects in information processing, which prevent the information in microscopic objects like atomsor photons from being observed or copied accurately, were long regarded as a mere nuisance, butare now known to make possible feats such as quantum cryptography, quantum teleportation anddramatic computational speedups. Although progress toward a practical quantum computer is slow,other surprising quantum informational effects continue to be discovered, and quantumcryptographic systems are already available commercially. Most importantly, the quantumapproach has led to a more coherent and powerful way of thinking about how physical objectsinteract and influence one another, and how that interaction can be used to compute, communicate,and protect privacy. This talk will avoid mathematical complications and instead aim to explaincentral quantum concepts like entanglement, which at first sight seem counterintuitive.

Giulio Chiribella (Tsinghua)

**The Heisenberg limit for information replication**

No process in nature can perfectly copy an arbitrary quantum state. But is it possible to engineer

processes that copy quantum states with vanishingly small error? And in the affirmative case, how many copies can these processes produce? In this talk I will show that the precision limits of

quantum metrology determine the answer to these questions: On the one hand, the Standard

Quantum Limit implies that deterministic copy machines can only produce a negligible number of

high-quality extra copies. On the other hand, probabilistic copy machines need only to obey a

Heisenberg Limit, which permits them to produce a large number of nearly perfect replicas. In

particular, I will show the possibility of super-replication phenomena where N equally prepared

quantum clocks can be transformed into a much larger number of M nearly perfect copies where

M can be any number that is small compared to the square of N. Finally, I will discuss the tradeoff between the number of high-quality copies produced by a process and the probability that the process takes place, providing the exact rate at which the probability has to decrease in order to achieve super-replication.

Yun Shang (AMSS)

**Computing power of Turing machines based on quantum logic**

In this paper, we present recursion theoretical characterizations of the computational power of

quantum Turing machines based on quantum logic. For unsharp quantum logic, let a lattice

ordered quantum multiple-valued (QMV) algebra be its truth value lattice. When lattice ordered

QMV algebras satisfy locally finite condition (that is, every non zero element has finite order) and

its meet operation is computable, it is proved that , whereand and denote the class of quantum languages accepted by these Turing machines inthe depth-first method and the width-first method, respectively. For sharp quantum logic, similarresults are obtained for a general orthomodular truth value lattice.

Yuan Feng (UTS)

**Symbolic bisimulation for quantum processes**

With the previous notions of bisimulation presented in the literature, to check if two quantum

processes are bisimilar, we have to instantiate their free quantum variables with arbitrary quantumstates. This makes checking bisimilarity infeasible from an algorithmic point of view, as quantumstates constitute a continuum. In this talk, we introduce a symbolic operational semantics for quantum processes directly at the quantum operation level, which allows us to describe the bisimulation between quantum processes without resorting to quantum states. We show that the symbolic bisimulation defined here is equivalent to the open bisimulation for quantum processes in previous work, but allows an efficient implementation for bisimilarity check. We also give a

modal logical characterisation for quantum bisimilarity based on an extension of Hennessy-Milner logic to quantum processes.

Bo Qi (AMSS)

**Quantum State Tomography via Linear Regression Estimation**

A simple yet efficient method of linear regression estimation (LRE) is presented for quantum state

tomography. In this method, quantum state reconstruction is converted into a parameter estimation problem of a linear regression model and the least-squares method is employed to estimate the unknown parameters. An asymptotic mean squared error (MSE) upper bound for all possible states to be estimated is given analytically, which depends explicitly upon the involved measurement bases. This analytical MSE upper bound can guide one to choose optimal

measurement sets. The computational complexity of LRE is O(d4) where d is the dimension of the

quantum state. Numerical examples show that LRE is much faster than maximum-likelihood estimation for quantum state tomography.

Runyao Duan (UTS)

**Zero-error classical channel capacity and simulation cost assisted by quantum**

**non-signalling correlations**

We study the one-shot zero-error classical capacity of quantum channels assisted by quantum

non-signalling correlations, and the reverse problem of exact simulation. Both lead to simple

semi-definite programmings whose solutions can be given in terms of the conditional min-entropies. We show that the asymptotic simulation cost is precisely the conditional

min-entropy of the Choi-Jamiolkowski matrix of the given channel. For classical-quantum

channels, the asymptotic capacity is reduced to a quantum fractional packing number suggested by Harrow, which leads to an operational interpretation of the celebrated Lovasz theta function as the zero-error classical capacity of a graph assisted by quantum non-signalling correlations. This talk is based on a joint work with Andreas Winter (UAB).