AMSS-UTS Joint Workshop on Quantum Computing

主办方：中国科学院数学与系统科学研究院   澳大利亚悉尼科技大学

 

时间:

2020年12月14日-16日

 

直播地址:

 

特邀报告人:

会议组织者:

会务组成员：

 

会议日程:

 

报告摘要：

Yuan Feng (University of Technology Sydney)

Title: Quantum Hoare logic with classical variables

Abstract: Hoare logic provides a syntax-oriented 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 classical-quantum 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 decision-diagram 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 best-known classical algorithms.

 

Yinan Li (Nagoya University)

Title: Quantum algorithms for matrix scaling and matrix balancing

Abstract: Matrix scaling and matrix balancing are two basic linear-algebraic problems with a wide variety of applications, such as approximating the permanent, and pre-conditioning 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 speed-ups 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.

 

Jin-Peng 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 n-dimensional 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 infinite-dimensional 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 worst-case 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 so-called 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 non-uniform 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 StoqMA-complete (as a comparison, distinguishing quantum circuits is QMA-complete [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.

 

Zi-Wen Liu (Perimeter Institute for Theoretical Physics)

Title: No-go 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 well-behaved 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 widely-used graph states, such as 1-D and 2-D cluster states with translation-invariance symmetry, and the Greenberger-Horne-Zeilinger 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 permutation-invariant 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 two-dimensional 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 (quantum-secure) one-way 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: Space-Depth Trade-Off of CNOT Circuits

Abstract: Due to the decoherence of the state-of-the-art 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 n-qubit CNOT circuit could be parallelized to $O(log n)$ depth, with $O(n^2)$ ancillae. In this work, we establish an asymptotically optimal space-depth trade-off for the design of CNOT circuits. We prove that for any $m\ge 0$, any n-qubit 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 information-theoretically meaningful way. In particular, every previously defined entanglement measure bearing a precise information-theoretic meaning is not known to be efficiently computable, or if it is efficiently computable, then it is not known to have a precise information-theoretic meaning. In this work, we meet this challenge by introducing an entanglement measure that has a precise information-theoretic 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 quantum-physical experiments. (The talk is based on arXiv:2007.14270, 1904.10437, 1809.09592.)

 

Xiao-Di Wu (University of Maryland, College Park)

Title: Computational Thinking Toward End-to-End 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 information-processing 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 end-to-end 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 meta-programming framework for automating NISQ application design, and a practical verification scheme for quantum supremacy. 

 

Penghui Yao (Nanjing University)

Title: Non-local 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 non-interactive 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 many-body physics. In this talk, we introduce a framework of the hybrid tensor network consisting of classical low-rank tensors and many-body 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 many-body 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 task-tailored 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 C|0？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 information-theoretically (IT) secure or based on trapdoor assumptions (public key encryptions). In this paper we study how the availability of symmetric-key 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 IT-secure 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: Projection-Based 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 Birkhoff-von 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 projection-based 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 measurement-restricted 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 Harrow-Hassidim-Lloyd algorithm and Shor's algorithm.