Lectures on classical simulation of quantum computations – Richard Jozsa

From next week Professor Richard Jozsa (from Cambridge) will be visiting UTS to do some work with our group. He will also be giving a couple of lectures on the classical simulation of quantum computations. Richard is without question one of the world’s authorities on this subject, and an excellent speaker. So, if you get the chance to come along you definitely should!
Details below.Lectures on classical simulation of quantum computations

Lecturer: Professor Richard Jozsa, DAMTP, University of Cambridge UK.

Dates: Lecture 1, 4 April 2016; Lecture 2, 6 April 2016 (see detailed information below)

Lecture 1. Theory of Clifford operations.

Venue: CB10.03.460 (Room 460, Level 3, UTS City Campus Building 10), 235 Jones Street, Ultimo, NSW 2007
Time: 2-5PM (3-3:30PM: Tea break; 4:30-5PM: Free discussions)

Date: Monday, 4 April 2016

Introduction to Pauli and Clifford operations for qudits; construction of the metaplectic representation and the discrete Wigner function; a hidden variable model for Clifford circuits; implications for classical simulability.

Based mainly on ingredients from:

D. Gross  arXiv:quant-ph/0702004
V. Veitch, C. Ferrie, D. Gross, J. Emerson  arXiv:1201.1256

R. Jozsa, M. Van den Nest  arXiv:1305.6190

Lecture 2. Theory of matchgate (MG) computations.

Venue: CB02.04.010 (Room 10, Level 4, UTS City Campus Building 2), 15 Broadway, Broadway, NSW 2007

Time: 2-5PM (3-3:30PM: Tea break; 4:30-5PM: Free discussions)

Date: Wednesday, 6 April 2016

Introduction to MGs and relation to fermionic modes; MGs and partition functions for some solvable classical spin models; classical simulability of MG circuits with arbitrary input product states, intermediate measurements and adaptive choices of subsequent gates, and multi-line outputs, all being included simultaneously (D. Brod 2016). Further issues if time permits.

Based mainly on ingredients from:

B. Terhal, D. DiVincenzo  arXiv:quant-ph/0108010
D. Brod  arXiv:1602.03539
R. Jozsa, A. Miyake  arXiv:0804.4050
R. Jozsa, A. Miyake, S. Strelchuk  arXiv:1311.3046

Seminar announcement: Youming Qiao

Title: Quantum matching problems

Speaker: Youming Qiao, UTS

Time/Location: 2-3pm, 16 March 2016 (Wed) / CB10.02.410, UTS

Abstract: We describe two algorithmic problems, both of which can be viewed as quantum analogues of the perfect matching problem on bipartite graphs. Given several square matrices, we are asked to:
(1) decide if there is a full-rank matrix in the linear span of them;
(2) decide if there is a shrunk subspace. That is a subspace U, s.t. the union of the images under these matrices is of smaller dimension than U.

The first problem is the well-known polynomial identity testing problem, for which a deterministic efficient solution implies a strong arithmetic circuit lower bound. The second problem has a rich history and has appeared in various forms in a remarkable number of mathematical and computational areas. For example, it is a key problem in the theory of arithmetic circuits with divisions, as recently studied by Hrubeš and Wigderson. After introducing these problems, we will present a couple of ingredients in a recent deterministic efficient algorithm for the second problem. These include a polynomial degree upper bound on generating the ring of matrix semi-invariants, and a linear algebraic analogue of the augmenting path technique.

Based on joint works with Gábor Ivanyos and K. V. Subrahmanyam, arXiv:1508.00690 and arXiv:1512.03531. Another recent paper on this topic is arxiv:1511.03730.

Seminar announcement: Mingsheng Ying

Title: Toward Automatic Verification of Quantum Programs
Speaker: Mingsheng Ying, UTS
Time/Location: 2-3pm, 9 March 2016 (Wed) / CB11.06.408, FEIT Seminar Room
Programming is error-prone. It is even worse when programming a quantum computer or designing quantum communication protocols, because human intuition is much better adapted to the classical world than to the quantum world? How can we build automatic tools for verifying correctness of quantum programs and quantum communication protocols? A logic for verification of both partial correctness and total correctness of quantum programs was developed in our paper [TOPLAS’2011, art. no. 19]. The (relative) completeness of this logic was proved. Recently, a theorem prover for automatic verification of partial correctness of quantum programs was built based on our logic [arXiv: 1601.03835]. To further develop automatic tools for verifying total correctness of quantum programs, we are working on techniques for synthesis of ranking functions that guarantee termination of quantum programs.
1. Partial correctness: for any input satisfying the precondition, if the program terminates, then the output satisfies the postcondition.
2. Total correctness: for any input satisfying the precondition, the program terminates and the output satisfies the postcondition.

My talk at the Workshop on the Frontiers of Quantum Information and Computer Science

Back in September 2015 I was invited to present a seminar at the Workshop on Quantum Information and Computer Science, hosted by the Joint Centre for Quantum Information and Computer Science at the University of Maryland. (Video above and slides are here.)

My talk was on a recent paper that I wrote together with Ashley Montanaro and Dan Shepherd where we generalized the Boson Sampling argument of Aaronson and Arkhipov to spin systems. We argued that IQP Sampling, the process of sampling from IQP (Instantaneous Quantum Polytime) circuits, can not be efficiently simulated on classical computers to within a constant variation distance assuming a couple of plausible complexity theoretic conjectures.

Why is this interesting? Our argument demonstrates that the dynamics of randomly chosen Ising models can not be classically simulated – so we have identified one of the simplest physical systems that demonstrates so-called quantum supremacy.

Seminar announcement: Zhengfeng Ji

Title: Zero-knowledge proofs for QMA

Speaker: Zhengfeng Ji, UTS
Time/Location: Feb 24 (WED), 2-3pm / CB10.02.320, UTS

Abstract: In this talk, we will discuss the construction of zero-knowledge proof systems for QMA. We will talk about the difficulties and several ideas that helped in the final construction, including a new variant of the local Hamiltonian problem, the reduction to ZK for NP, and the use of quantum authentication codes to force the application of desired measurement.

This is based on a joint work with A. Broadbent, F. Song and J. Watrous.