AMSSUTS Joint Workshop on Quantum Computing
主辦方：中國科學院數學與系統科學研究院 澳大利亞悉尼科技大學
時間:
2020年12月14日16日
直播地址:
特邀報告人:
馮 元 悉尼科技大學

宋 方 波特蘭州立大學

洪 鑫 悉尼科技大學

孫曉明 中科院計算技術研究所

李彤陽 麻省理工學院

王 鑫 百度研究院量子計算研究所

李繹楠 名古屋大學

伍驍迪 馬里蘭大學

劉錦鵬 馬里蘭大學

姚鵬暉 南京大學

劉宇攀 希伯來大學

袁 驍 北京大學

劉子文 圓周理論物理研究所

張佳瑜 波士頓大學

馬雄峰 清華大學

支麗紅 中國科學院數學與系統科學研究院

尚 云 中國科學院數學與系統科學研究院

周 立 德國馬克斯普朗克研究所

會議組織者:
尚云 中國科學院數學與系統科學研究院

季錚鋒 悉尼科技大學

會務組成員：
李萌 15611519216

石驍 13269270853

李昕瑩 13130409070

會議日程:
報告摘要：
Yuan Feng (University of Technology Sydney)
Title: Quantum Hoare logic with classical variables
Abstract: Hoare logic provides a syntaxoriented method to reason about program correctness and has been proven effective in the verification of classical and probabilistic programs. Existing proposals for quantum Hoare logic either lack completeness or support only quantum variables, thus limiting their capability in practical use. We propose a quantum Hoare logic for a simple while language which involves both classical and quantum variables. Its soundness and relative completeness are proven for both partial and total correctness of quantum programs written in the language. Remarkably, with novel definitions of classicalquantum states and corresponding assertions, the logic system is quite simple and similar to the traditional Hoare logic for classical programs. Finally, a series of practical quantum algorithms, in particular the whole algorithm of Shor's factorization, are formally verified to show the effectiveness of the logic.
Xin Hong (University of Technology Sydney)
Title: A Tensor Network based Decision Diagram for Representation of Quantum Circuits
Abstract: Tensor networks have been successfully applied in simulation of quantum physical systems for decades. Recently, they have also been employed in classical simulation of quantum computing, in particular, random quantum circuits. In this presentation, I will introduce a decisiondiagram style data structure, called TDD (Tensor Decision Diagram), for more principled and convenient applications of tensor networks. This new data structure provides a compact and canonical representation for quantum circuits. By exploiting circuit partition, the TDD of a quantum circuit can be computed efficiently. It is expected that TDDs will play an important role in various design automation tasks related to quantum circuits, including but not limited to equivalence checking, error detection, synthesis, simulation, and verification. The presented work is available at https://arxiv.org/abs/2009.02618.
Tongyang Li (Massachusetts Institute of Technology)
Title: Quantum algorithms for convex and nonconvex optimization
Abstract: The theories of optimization answer foundational questions in machine learning and lead to new algorithms for practical applications. In this talk, I will introduce two quantum algorithms that we recently developed for convex optimization (arXiv:1809.01731) and nonconvex optimization (arXiv:2007.10253), respectively. Both achieve polynomial quantum speedup compared to the bestknown classical algorithms.
Yinan Li (Nagoya University)
Title: Quantum algorithms for matrix scaling and matrix balancing
Abstract: Matrix scaling and matrix balancing are two basic linearalgebraic problems with a wide variety of applications, such as approximating the permanent, and preconditioning linear systems to make them more numerically stable. We study the power and limitations of quantum algorithms for these problems. We provide quantum implementations of two classical methods: Sinkhorn's algorithm for matrix scaling and Osborne's algorithm for matrix balancing. Using amplitude estimation as our main tool, our quantum implementations achieve polynomial speedups for both problems in terms of the matrix size, at the expense of a worse polynomial dependence on the error. We also prove a matching lower bound, showing that our quantum algorithm for matrix scaling is essentially optimal for constant error.
This talk is based on joint work with Joran van Apeldoorn, Sander Gribling, Harold Nieuwboer, Michael Walter and Ronald de Wolf.
JinPeng Liu (University of Maryland)
Title: Efficient quantum algorithm for dissipative nonlinear differential equations
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 ndimensional ordinary differential equations. Assuming R < 1, where R is a parameter characterizing the ratio of the nonlinearity to the linear dissipation, this algorithm has complexity T^2 poly(log T, log n)/epsilon, where T is the evolution time and epsilon is the allowed error in the output quantum state. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. We achieve this improvement using the method of Carleman linearization, for which we give an improved convergence theorem. This method maps a system of nonlinear differential equations to an infinitedimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worstcase complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for R >= \sqrt{2}. Finally, we discuss potential applications of this approach to problems arising in biology as well as in fluid and plasma dynamics.
Yupan Liu (The Hebrew University of Jerusalem)
Title: StoqMA meets distribution testing
Abstract: StoqMA captures the computational hardness of approximating the ground energy of local Hamiltonians that do not suffer the socalled sign problem. We provide a novel connection between StoqMA and distribution testing via reversible circuits. First, StoqMA with easy witness (eStoqMA) is contained in MA, where easy witness is a nonuniform generalization of a subset state such that the associated set's membership can be efficiently verifiable. The proof follows from distribution testing techniques, which infers a simplified proof of StoqMA with perfect completeness is contained in MA [BBT06]. Second, by showing distinguishing reversible circuits with random ancillary bits is StoqMAcomplete (as a comparison, distinguishing quantum circuits is QMAcomplete [JWB03]), we construct a soundness error reduction of StoqMA. Additionally, we show that both variants of StoqMA that without any random ancillary bit and with perfect soundness are contained in NP. Our results make a step towards collapsing the hierarchy MA, StoqMA, SBP, in which all classes are contained in AM and collapse to NP under derandomization assumptions. The paper is available on arxiv:2011.05733.
ZiWen Liu (Perimeter Institute for Theoretical Physics)
Title: Nogo theorems for quantum resource purification: Theory and applications
Abstract: The manipulation of quantum “resources” such as entanglement and coherence lies at the heart of quantum science and technology, empowering potential advantages over classical methods. In practice, a particularly important kind of manipulation is to “purify” the quantum resources, since they are inevitably contaminated by noises and thus often lost their power or become unreliable for direct usage. In this work, we establish a theory of the universal limitations on the accuracy and efficiency of resource purification tasks which apply to any wellbehaved resource theory, for both state (static) and channel (dynamical) resources. The general results bring new insights and imply various forms of fundamental limits to a broad range of problems of great theoretical and practical importance, including magic state distillation and fault tolerant quantum computing, quantum error correction, quantum Shannon theory, and quantum circuit synthesis. I shall discuss certain cases in more detail depending on interests of the audience.
Xiongfeng Ma (Tsinghua University)
Title: Genuine multipartite entanglement in a symmetric system
Abstract: Recently, there are tremendous developments on the number of controllable qubits in several quantum computing systems. For these implementations, it is crucial to certify the entanglement of the prepared multipartite quantum state as a base for further information processing. In this talk, I shall present a systematic method using very few local measurements to detect multipartite entanglement structures based on graph states. For several widelyused graph states, such as 1D and 2D cluster states with translationinvariance symmetry, and the GreenbergerHorneZeilinger state, by taking advantage of the area law of entanglement entropy, we derive analytical solutions for the witnesses, with only employing two local measurements. Meanwhile, I shall also introduce an efficient method to decompose multipartite observables with permutation symmetry using only $(N+1)(N+2)/2$ local measurement settings, with $N$ the number of qubits. This method is particularly effective for the fidelity estimation and entanglement detection of permutationinvariant states, such as the W state and Dick states.
Yun Shang (Academy of Mathematics and System Sciences,CAS)
Title：Generalized exceptional quantum walk search
Abstract: We mainly study exceptional configuration for coined quantum walk search. For searching on a twodimensional grid by AKR algorithm, we find some new classes of exceptional configurations that cannot be found by the AKR algorithm effectively and the known diagonal configuration can be regarded as its special case. Meanwhile, we give two modified quantum walk models that can improve the success probability in the exceptional configurations by numerical simulation. Furthermore, we introduce the concept of generalized exceptional configuration and consider search by quantum walk on a cycle with Grover coin. We find that the most common coin combination model (G, ？), where G is a Grover diffusion transformation, is a generalized exceptional configuration when just searching one marked vertex on the cycle. In the end, we find generalized exceptional configuration has a different evolution of quantum coherence from exceptional configuration. These extend largely the range of exceptional configuration of quantum walk search in some sense. This talk is based on Arxiv:2011.01629.
Fang Song (Portland State University)
Title : Oblivious transfer is in miniQCrypt
Abstract: What is the minimum assumption to realize oblivious transfer, a fundamental primitive in modern cryptography? In this talk, I will show a quantum oblivious transfer protocol assuming existence of a (quantumsecure) oneway function only, which is essentially tight. This settles a long line of pursuit in the literature, which I will give an account of. Based on joint work with Alex Grilo, Huijia (Rachel) Lin, and Vinod Vaikuntanathan.
Xiaoming Sun (Institute of Computing Technology,CAS)
Title: SpaceDepth TradeOff of CNOT Circuits
Abstract: Due to the decoherence of the stateoftheart physical implementations of quantum computers, it is essential to parallelize the quantum circuits to reduce their depth. Two decades ago, Moore and Nilsson demonstrated that additional qubits (or ancillae) could be used to design “shallow” parallel circuits for quantum operators. They proved that any nqubit CNOT circuit could be parallelized to $O(log n)$ depth, with $O(n^2)$ ancillae. In this work, we establish an asymptotically optimal spacedepth tradeoff for the design of CNOT circuits. We prove that for any $m\ge 0$, any nqubit CNOT circuit can be parallelized to $O(max{log n; n^2/(n+m) log(n+m)})$ depth, with m ancillae. Our results can be directly extended to stabilizer circuits using an earlier result by Aaronson and Gottesman. In addition, we provide relevant hardness evidences for synthesis optimization of CNOT circuits in term of both size and depth.
Xin Wang (Institute for Quantum Computing at Baidu Research)
Title: Cost of quantum entanglement simplified
Abstract: Quantum entanglement is a key physical resource in quantum information processing that allows for performing basic quantum tasks such as teleportation and quantum key distribution. Ever since the rise of quantum information theory, it has been an open problem to quantify entanglement in an informationtheoretically meaningful way. In particular, every previously defined entanglement measure bearing a precise informationtheoretic meaning is not known to be efficiently computable, or if it is efficiently computable, then it is not known to have a precise informationtheoretic meaning. In this work, we meet this challenge by introducing an entanglement measure that has a precise informationtheoretic meaning as the exact cost required to prepare an entangled state when two distant parties are allowed to perform quantum operations that completely preserve the positivity of the partial transpose. Additionally, this entanglement measure is efficiently computable by means of a semidefinite program, and it bears a number of useful properties such as additivity and faithfulness. Our results bring key insights into the fundamental entanglement structure of arbitrary quantum states, and they can be used directly to assess and quantify the entanglement produced in quantumphysical experiments. (The talk is based on arXiv:2007.14270, 1904.10437, 1809.09592.)
XiaoDi Wu (University of Maryland, College Park)
Title: Computational Thinking Toward EndtoEnd Quantum Applications
Abstract: Computational Thinking is the thought processes involved in formulating problems and their solutions so that the solutions are represented in a form that can be effectively carried out by an informationprocessing agent. In this talk, I will demonstrate how computational thinking can help us identify research opportunities where the ideas from computer science can help contribute to the implementation of endtoend quantum applications. I will briefly mention projects guided by this principle in my group with some more details on the projects of a certified optimizing compiler for quantum circuits, a metaprogramming framework for automating NISQ application design, and a practical verification scheme for quantum supremacy.
Penghui Yao (Nanjing University)
Title: Nonlocal games with noisy maximally entangled states are decidable
Abstract: This talk considers a special class of nonlocal games, where the players are allowed to share infinitely many copies of noisy maximally entangled states, which can be obtained by deplolarzing maximally entangled states by an arbitrarily small noise. We prove an upper bound on the copies of the shared states for the players to approximate the value of the game (the supremum of the probablity that the players win the games) to an arbitrarily small precision. Combining with the recent breakthrough work MIP*=RE by Ji, Natarajan, Vidick, Wright and Yuen, our result implies that nonlocal games are not robust against the noise from the preshared states.
The structure of the proofs is built on the recent framework about the decidability of the noninteractive simulation of joint distributions with significant generalization. The paper develops a series of new techniques about the Fourier analysis on matrix spaces and proves a quantum invariance principle and a hypercontractive inequality for random operators. These novel tools are interesting on their own right and may have other applications in quantum information theory and quantum complexity theory.
Xiao Yuan (Peking University)
Title: Quantum simulation with hybrid tensor networks
Abstract: Tensor network theory and quantum simulation are respectively the key classical and quantum computing methods in understanding quantum manybody physics. In this talk, we introduce a framework of the hybrid tensor network consisting of classical lowrank tensors and manybody quantum states. By leveraging the ability of tensor networks in the efficient classical representation of quantum states, we extend the power of NISQ devices to represent manybody quantum systems with a small quantum processor. With the example of hybrid tree tensor networks, we demonstrate how to use a small quantum processor to efficiently represent large quantum systems preserving certain properties. Our result provides a unified framework for the existing tasktailored schemes and could be applicable in quantum chemistry, condensed matter and quantum field theory.
Jiayu Zhang (Boston University)
Title: Succinct blind quantum computation using a random oracle
Abstract: In the universal blind quantum computation problem, a client wants to make use of a single quantum server to evaluate C0？where C is an arbitrary quantum circuit while keeping C secret. The client's goal is to use as few resources as possible. This problem, first raised by Broadbent, Fitzsimons and Kashefi [FOCS09, arXiv:0807.4154], has become fundamental to the study of quantum cryptography, not only because of its own importance, but also because it provides a testbed for new techniques that can be later applied to related problems (for example, quantum computation verification). Known protocols on this problem are mainly either informationtheoretically (IT) secure or based on trapdoor assumptions (public key encryptions). In this paper we study how the availability of symmetrickey primitives, modeled by a random oracle, changes the complexity of universal blind quantum computation. We give a new universal blind quantum computation protocol. Similar to previous works on ITsecure protocols (for example, BFK [FOCS09, arXiv:0807.4154]), our protocol can be divided into two phases. In the first phase the client prepares some quantum gadgets with relatively simple quantum gates and sends them to the server, and in the second phase the client is entirely classical  it does not even need quantum storage. Crucially, the protocol's first phase is succinct, that is, its complexity is independent of the circuit size. Given the security parameter κ, its complexity is only a fixed polynomial of κ, and can be used to evaluate any circuit (or several circuits) of size up to a subexponential of κ. In contrast, known schemes either require the client to perform quantum computations that scale with the size of the circuit [FOCS09, arXiv:0807.4154], or require trapdoor assumptions [Mahadev, FOCS18, arXiv:1708.02130].
Lihong Zhi (Academy of Mathematics and System Sciences, CAS)
Title: Infinite Dimensional Quantum Strassen Theorem
Abstract: Strassen's theorem circa 1965 gives necessary and sufficient conditions on the existence of a probability measure on two product spaces with given support and two marginals. In the case where each product space is finite Strassen's theorem is reduced to a linear programming problem which can be solved using flow theory.
A density matrix of bipartite quantum system is a quantum analog of a probability matrix on two finite product spaces. Partial traces of the density matrix are analogs of marginals. The support of the density matrix is its range. The analog of Strassen's theorem in this case can be stated and solved using semidefinite programming. The aim of this paper is to give analogs of Strassen's theorem to density trace class operators on a product of two separable Hilbert spaces, where at least one of the Hilbert spaces is infinite dimensional.
Joint work with Shmuel Friedland and Jingtong Ge https://arxiv.org/abs/1905.06865
Li Zhou (Max Planck Institute)
Title: ProjectionBased Runtime Assertions for Testing and Debugging Quantum Programs
Abstract: In this talk, I'll introduce a runtime assertion scheme for testing and debugging quantum programs on a quantum computer. The predicates are represented by projections (or equivalently, closed subspaces of the state space), following Birkhoffvon Neumann quantum logic. The satisfaction of a projection by a quantum state can be directly checked upon a small number of projective measurements rather than a large number of repeated executions. On the theory side, we rigorously prove that checking projectionbased assertions can help locate bugs or statistically assure that the semantic function of the tested program is close to what we expect, for both exact and approximate quantum programs. On the practice side, we consider hardware constraints and introduce several techniques to transform the assertions, making them directly executable on the measurementrestricted quantum computers. We also propose to achieve simplified assertion implementation using local projection technique with soundness guaranteed. We demonstrate the effectiveness and efficiency by its applications to assert two sophisticated quantum algorithms, the HarrowHassidimLloyd algorithm and Shor's algorithm.