Congratulations to Prof Zhengfeng Ji from the Quantum Computation (QC) Laboratory in QCIS and co-authors who just presented two papers at the 48th ACM Symposium on the Theory of Computing (STOC 2016) in Cambridge Massachusetts on June 21, 2016. STOC is the premier conference for theoretical computer science research, and is regarded one of the most competitive conferences across all fields of computer science.
In a single-author paper titled “Classical Verification of Quantum Proofs”, Prof Ji constructed a classical interactive protocol that verifies the validity of a quantum witness state for local Hamiltonian problems. This provides an example where multiple entangled provers can convince a classical verifier of certain facts that classical provers cannot, under reasonable complexity assumptions. More technically, the paper presents a method that allows one to embed Kitaev's local Hamiltonian problem into Bell inequalities, thereby building an interesting connection between quantum Hamiltonian complexity on one hand and the study of non-local games on the other. The work reveals the power of entangled provers and stimulates further investigation of quantum multi-prover systems.
In another paper titled “Sample-Optimal Tomography of Quantum States”, Prof Ji and his co-authors from MIT, the University of Waterloo, and University of Oregon, established the sample complexity of quantum tomography. Quantum tomography is the procedure for obtaining the classical description of a quantum state, and is a widely used fundamental primitive in quantum information. The paper completely answers the question of how many copies of a quantum state one needs in order to perform quantum state tomography, which is of key importance to experimental quantum computing. Dr Nengkun Yu, one of the paper’s co-authors, from the Institute for Quantum Computing (IQC) at the University of Waterloo will be joining the QC Lab this July as a UTS Chancellors’ Postdoctoral Researcher.
Details of papers can be found below:
Classical Verification of Quantum Proofs
Sample-Optimal Tomography of Quantum States
Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu
Information about the conference is available at http://acm-stoc.org/stoc2016/