CFCS Quantum Day organized by Center on Frontiers of Computing Studies (CFCS), Peking University will be held virtually on May 12th, 2021. The Quantum Day is a one-day seminar focusing on pioneering works on supremacy, quantum simulation, and applications with near-term quantum computing hardware. Given continued uncertainty surrounding the future of COVID-19 and worldwide travel precautions, CFCS Quantum Day will be a virtual-only event.

 

Agenda

 

 

Invited Talks

---

1. Fast Simulation of Planar Clifford Circuits

Prof. David Gosset, University of Waterloo

Abstract
Clifford circuits are a special family of quantum circuits that can be simulated on a classical computer in polynomial time using linear algebra. Recent work has shown that Clifford circuits composed of nearest-neighbor gates in planar geometries can solve certain linear algebra problems provably faster--as measured by circuit depth-- than classical computers. We don't know if these linear algebra tasks also admit polynomial quantum speedups in terms of total runtime (gate complexity). Motivated by this question, here we show that treewidth and planarity can be used to improve classical algorithms for simulating Clifford circuits. Our main result is a classical algorithm with runtime asymptotically upper bounded as n^{W/2} which samples from the output distribution obtained by measuring each qubit of a quantum planar graph state in given Pauli bases, where W is the matrix multiplication exponent. We also provide a classical algorithm with the same asymptotic runtime which samples from the output distribution of any constant-depth Clifford circuit in a planar geometry. This is joint work with Daniel Grier, Alex Kerzner, and Luke Schaeffer (arxiv:2009.03218).

Biography
David Gosset joined the Institute for Quantum Computing (IQC) as an Associate Professor in the Department of Combinatorics and Optimization at the University of Waterloo on August 1, 2018. Gosset received his PhD in Physics from MIT in 2011 under the supervision of Edward Farhi. He subsequently held postdoctoral fellowships at IQC and at Caltech, before joining the IBM T.J. Watson Research Center in 2016. Gosset's research focuses on Quantum algorithms, Classical simulation of quantum computation, Computational complexity of quantum many-body systems.

 

2. Efficient Quantum Algorithm for Dissipative Nonlinear Differential Equations

Prof. Andrew Childs, University of Maryland

Abstract
While there has been extensive previous work on efficient quantum algorithms for linear differential equations, analogous progress for nonlinear differential equations has been severely limited due to the linearity of quantum mechanics. Despite this obstacle, we develop a quantum algorithm for initial value problems described by dissipative quadratic ordinary differential equations. We also establish lower bounds on the worst-case complexity of quantum algorithms for nonlinear differential equations, identifying cases in which the problem is intractable.

This talk is based on joint work with Jin-Peng Liu, Herman Kolden, Hari Krovi, Nuno Loureiro, and Konstantina Trivisa.

Biography
Andrew Childs received a doctorate in physics from MIT in 2004, advised by Edward Farhi. After completing his Ph.D., Childs was a DuBridge Postdoctoral Scholar at the Institute for Quantum Information at the California Institute of Technology from 2004 to 2007. From 2007 to 2014, he was a faculty member in the Department of Combinatorics and Optimization and the Institute for Quantum Computing at the University of Waterloo. Childs joined the University of Maryland in 2014. He is also a senior fellow of the Canadian Institute for Advanced Research. Childs is known for his work on quantum computing, especially on the development of quantum algorithms.

 

3. The Quantum Complexity of the Closest Pair Problem

Dr. Chunhao Wang, Pennsylvania State University

Abstract
Given n points in a d-dimensional space, the goal is to find a pair of points with the smallest distance. In constant dimensions, we knew the classical upper/lower bounds and a quantum lower bound. When the dimension goes up to polylog(n), we knew classical upper and (conditional) lower bounds, as well as a quantum upper bound. In this talk, I will introduce the quantum upper bound of this problem in constant dimensions and the (conditional) quantum lower bound in polylog(n) dimensions. Both the bounds are tight (up to some poly-logarithmic factor). The upper bound (quantum algorithm) is based on quantum walk search, and the lower bound is based on quantum fine-grained reductions and a quantum version of the strong exponential-time hypothesis.

The talk is based on arXiv:1911.01973 and it will be accessible to a general computer science and mathematics audience without a quantum computing background.

Biography
Dr. Chunhao Wang is working as an assistant professor at Department of Computer Science and Engineering, Pennsylvania State University He got his Ph.D. degree from University of Waterloo in 2018 and has been a post-doctoral research fellow at the University of Texas at Austin from 2018 to 2020. Dr. Chunhao Wang’s research primarily focuses on the connection between physical systems and computation. He is particularly interested in quantum algorithms related to simulating physical systems as well as their implications to classical algorithms.

 

4. Quantum Algorithms for Semidefinite Programs with Applications to Machine Learning

Dr. Tongyang Li, Massachusetts Institute of Technology and Peking University

Abstract
Semidefinite programming has been a central topic in the study of mathematical optimization, theoretical computer science, and operations research in the last decades. In this talk, we introduce a quantum algorithms for solving SDPs with polynomial speedup compared to the best known classical algorithms. We also introduce how the quantum algorithm can be applied to training linear and kernel-based classifiers, as well as solving general matrix games. The talk is based on three papers: https://arxiv.org/abs/1710.02581, https://arxiv.org/abs/1904.02276, and https://arxiv.org/abs/2012.06519.

Biography
Tongyang Li is a postdoctoral associate at the Center for Theoretical Physics, Massachusetts Institute of Technology. He received Master and Ph.D. degrees from the Department of Computer Science, University of Maryland in 2018 and 2020, respectively. He received Bachelor of Engineering from Institute for Interdisciplinary Information Sciences, Tsinghua University and Bachelor of Science from Department of Mathematical Sciences, Tsinghua University, both in 2015. He was a recipient of the IBM Ph.D. Fellowship, the NSF QISE-NET Triplet Award, and the Lanczos Fellowship. His research focuses on designing quantum algorithms for machine learning and optimization.

 

5. Recent Advances in Predicting Properties of Quantum Systems

Hsin-Yuan Huang, California Institute of Technology

Abstract
I will present a rigorous and efficient procedure for converting a quantum system into a succinct classical description of the system, its classical shadow. Classical shadows can efficiently predict many properties of interest, including expectation values of local observables and entanglement entropy in local subsystems. Recently, progress has been made in experimentally realizing the procedure and extending the capability of classical shadows. For example, in an ongoing work, we show that efficient classical machine learning algorithms using classical shadows can address quantum many-body problems, such as classifying phases of matter.

Biography
Hsin-Yuan Huang is a Ph.D. student at California Institute of Technology (Caltech) advised by John Preskill and Thomas Vidick. During undergraduate, he studied computer science and physics; with previous research experiences in deep learning (at Allen Institute of AI and Microsoft Research AI), optimization, and statistical machine learning (with Prof. Chih-Jen Lin). He is mainly interested in the interplay between physics and information science (complexity theory, information theory, machine learning).

 

6. Fluxonium Qubits for Ultra-high-fidelity and Scalable Quantum Processors

Dr. Chunqing Deng, Quantum Scientist and Head of the Experimental Group, Alibaba Quantum Laboratory

Abstract
The success of superconducting quantum computing (SQC) has so far been largely built upon the transmon qubit. Finding an alternative qubit that drastically outperforms transmon represents one of the most fundamental and exciting frontiers of SQC. The fluxonium qubit stands out as a promising candidate, due to its long coherence times and large anharmonicity. Furthermore, fluxonium can be directly integrated into the existing circuit-QED schemes for scaling. For these reasons, fluxonium is our qubit platform of choice at Alibaba Quantum Laboratory.

In this talk, I will present our design and experiments of a 2D fluxonium circuit, which exhibits high coherence, high tunability and strong coupling. With T1 and T2 > 100 us at around the sweet spot, we achieve a dielectric loss tangent as low as 0.7e-6, approaching the state of the art. Using a high-bandwidth flux bias, we demonstrate robust qubit reset and readout, together with fast one- and two-qubit gates. In particular, we realized an iSWAP two-qubit gate, achieving 0.995 fidelity. Our work paves the path toward a fluxonium-based, ultra-high-fidelity multi-qubit processor.

Biography
Chunqing Deng is a Quantum Scientist at Alibaba Quantum Lab (AQL). He received his BSc from Peking University in 2008 and his PhD from University of Waterloo in 2015. After that, he joined D-Wave Systems Inc. and became a lead scientist there. At D-Wave Systems, Chunqing worked on improving the coherence of superconducting qubits and developing novel qubit-qubit interactions for future-generation adiabatic quantum processors. He is currently leading the experimental quantum computing effort at Alibaba to build a quantum computer for real-world problems.

 

7. Computation with Tensor Networks

Prof. Pan Zhang, Chinese Academy of Sciences

Abstract
In this talk, Pan Zhang will present methods and algorithms for solving statistical mechanics problems, combinatorial optimization problems, and quantum circuit simulations, in an integrated framework based on tensor networks.

In statistical mechanics problems, the partition function (i.e. the normalization factor of the Boltzmann distribution) at a finite temperature can be obtained by contracting a tensor network that is converted from the stat. mech. problem. When equipped with the "Tropical" algebra, the tensor network contraction can be used to obtain ground state energy and entropy of the model directly at zero temperature. When the interactions in the stat. mech. model are complex, computing the partition function acts as estimating the amplitude of an end state basis vector of a quantum circuit, thus tensor network contractions can be used to simulate quantum circuits. Pan Zhang will introduce approximate and exact algorithms for contracting tensor networks, and their wide applications, particularly in simulating Google's Sycamore quantum circuits.

Biography
Pan Zhang is working as a professor at the Institute of theoretical physics, Chinese academy of sciences (ITP, CAS). He got his Ph.D. degree from Lanzhou University in 2009 and has been a post-doctoral research fellow at the Santa Fe Institute before joining ITP, CAS in 2015. Pan Zhang’s research is in the interdisciplinary field of statistical physics, machine learning, quantum many-body, and quantum computation.

 

8. Quantum Simulation with Hybrid Tensor Networks

Dr. Xiao Yuan, Peking University

Abstract
Tensor network theory and quantum simulation are respectively the key classical and quantum computing methods in understanding quantum many-body physics. Here, we introduce the framework of hybrid tensor networks with building blocks consisting of measurable quantum states and classically contractable tensors, inheriting both their distinct features in efficient representation of many-body wave-functions. With the example of hybrid tree tensor networks, we demonstrate efficient quantum simulation using a quantum computer whose size is significantly smaller than the one of the target system. We numerically benchmark our method for finding the ground state of 1D and 2D spin systems of up to 8*8 and 9*8 qubits with operations only acting on 8+1 and 9+1 qubits, respectively. Our approach sheds light on simulation of large practical problems with intermediate-scale quantum computers, with potential applications in chemistry, quantum many-body physics, quantum field theory, and quantum gravity thought experiments.

Biography
Dr. Xiao Yuan received his Bachelor in theoretical physics from Peking University in 2012 and got his PhD in physics from Tsinghua University in 2016. Then he worked as an assistant researcher at University of Science and Technology of China in 2017, as a postdoc at Oxford University from 2017 to 2019, and as a postdoc at Stanford University from 2019 to 2020. He is now an assistant professor at Center on Frontiers of Computing Studies, Peking University. My research interests focus on three aspects of quantum information science, including near-term and universal quantum computing, quantum foundation, and quantum cryptography.

 

9. Photonic Quantum Computational Advantage

Prof. Chao-Yang Lu, University of Science and Technology of China

Abstract
The main challenge for scaling up photonic quantum technologies is the lack of perfect quantum light sources. We have pushed the parametric down-conversion to its physical limit and produce two-photon source with simultaneously a collection efficiency of 97% and an indistinguishability of 96% between independent photons. Using a single quantum dot in microcavities, we have produced on-demand single photons with high purity (>99%), near-unity indistinguishability, and high extraction efficiency—all combined in a single device compatibly and simultaneously. Based on the high-performance quantum light sources, we have implemented boson sampling—which is an intermediate model of quantum computing, a strong candidate for demonstrating quantum computational advantage and refuting Extended Church Turing Thesis—with up to 76 photon clicks after a 100-mode interferometer. The photonic quantum computer, Jiuzhang, yields an output state space dimension of 10^30 and a sampling rate that is 10^14 faster using the state-of-the-art simulation strategy on supercomputers.

Biography
Chao-Yang Lu obtained Bachelor's degree from the University of Science and Technology of China (USTC) in 2004, and PhD in Physics from the Cavendish Laboratory, University of Cambridge in 2011. Since 2011, he is a Professor of Physics at USTC. His current research interest includes quantum computation, solid-state quantum photonics, multiparticle entanglement, quantum teleportation, superconducting circuits, and atomic arrays.

 

10. Approximating Permanent of Random Matrices with Vanishing Mean

Prof. Zhengfeng Ji, University of Technology Sydney

Abstract
The algorithm and complexity of approximating the permanent of a matrix is an extensively studied topic. Recently, its connection with quantum supremacy and more specifically BosonSampling draws particular attention to the average-case approximation problem of the permanent of random matrices with zero or small mean value for each entry. Eldar and Mehraban (FOCS 2018) gave a quasi-polynomial time algorithm for random matrices with a mean of at least 1/polyloglog(n). In this talk, we will discuss how to improve the result, simplify the proof, and hopefully further motivate interests in understanding the central complexity theory conjectures supporting quantum supremacy claims. It is based on joint work with Zhihan Jin and Pinyan Lu.

Biography
Zhengfeng Ji is currently a professor in the Centre for Quantum Software and Information, School of Computer Science, Faculty of Engineering and Information Technology at UTS. He obtained his Ph.D. from Tsinghua University in 2007. Before joining UTS, he was a postdoctoral research fellow at the Perimeter Institute for Theoretical Physics and Institute for Quantum Computing, University of Waterloo. His recent research focuses on the quantum algorithm and complexity theory, quantum post-quantum cryptography, and quantum computer science in general.

---

 

Please scan the code below to get the live-streaming links:

 

 

Organizers

 

Zhengfeng Ji
Professor, University of Technology Sydney
Research Interests: Quantum Algorithm and Complexity Theory, Quantum Post-Quantum Cryptography, Quantum Computer Science in general.

 

Tongyang Li
Postdoctoral Associate, MIT & Assistant Professor, CFCS, Peking University
Research Interests: Quantum Algorithms for Machine Learning and Optimization

 

Xiao Yuan
Assistant Professor , CFCS, Peking University
Research Interests: Quantum Computing, Quantum Information, Quantum Resource Theories

 

About CFCS

Founded in December 2017, CFCS is a university new initiative co-founded by Turing Award Winner Professor John Hopcroft and Professor Wen Gao. Currently there are 8 faculty members, and 3 more joining in this Fall. The center has established close collaboration with the world leading universities and leading institutions, enjoying frequent academic visits by scholars from around the world. There are 4 visiting chair professors at CFCS, including 2 additional Turing Award winners: Professors Silvio Micali from MIT, and Manuel Blum from CMU.

The center stands in the frontier of theoretical computer science, such as game theory, information theory, quantum information science and cryptography, applied computing, such as visual computing and artificial intelligence, as well as the interdisciplinary research in robotics, computational economics, and art, to name just a few.    

The center aims at developing the excellence on two fronts: research and education. On the research front, the center provides a world-class research environment, where innovation and impactful research is the central aim, measured by professional reputation among world scholars. On the education front, the center is deeply involved in the Turing Class, an elite undergraduate program that draws the cream of the crop from the PKU undergraduate talent pool. New curriculum and pedagogy are designed and practiced in this program, cultivating a new generation of computer scientists and engineers who are solid in both theories and practices.