Quantum Computing and Quantum Information Processing 2013
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
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).