We introduce the notion of quantum Markov decision process (qMDP) as a semantic model of nondeterministic and concurrent quantum programs. It is shown by examples that qMDPs can be used in analysis of quantum algorith...
详细信息
We introduce the notion of quantum Markov decision process (qMDP) as a semantic model of nondeterministic and concurrent quantum programs. It is shown by examples that qMDPs can be used in analysis of quantum algorithms and protocols. We study various reachability problems of qMDPs both for the finite-horizon and for the infinite-horizon. The (un)decidability and complexity of these problems are settled, and the relationship between one of them and the joint spectral radius problem, a long-standing open problem in matrix analysis and control theory, is clarified. Some of these results show a certain separation between the MDP and qMDP models. We also develop an algorithm for finding an optimal scheduler for a large class of qMDPs. Finally, the results of reachability problems are applied in the analysis of the safety problem for qMDPs. (C) 2018 Elsevier Inc. All rights reserved.
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 quantumHoare logic ei...
详细信息
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 quantumHoare logic either lack completeness or support only quantum variables, thus limiting their capability in practical use. In this article, we propose a quantum Hoare logic for a simple while language that 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. Furthermore, to simplify reasoning in real applications, auxiliary proof rules are provided that support standard logical operation in the classical part of assertions and super-operator application in the quantum part. Finally, a series of practical quantum algorithms, in particular the whole algorithm of Shor's factorisation, are formally verified to show the effectiveness of the logic.
We introduce the notion of linear ranking super-martingale (LRSM) for quantum programs (with nondeterministic choices, namely angelic and demonic choices). Several termination theorems are established showing that the...
详细信息
We introduce the notion of linear ranking super-martingale (LRSM) for quantum programs (with nondeterministic choices, namely angelic and demonic choices). Several termination theorems are established showing that the existence of the LRSMs of a quantum program implies its termination. Thus, the termination problems of quantum programs is reduced to realisability and synthesis of LRSMs. We further show that the realisability and synthesis problem of LRSMs for quantum programs can be reduced to an SDP (Semi-Definite programming) problem, which can be settled with the existing SDP solvers. The techniques developed in this paper are used to analyse the termination of several example quantum programs, including quantum random walks and quantum Bernoulli factory for random number generation. This work is essentially a generalisation of constraint-based approach to the corresponding problems for probabilistic programs developed in the recent literature by adding two novel ideas: (1) employing the fundamental Gleason's theorem in quantum mechanics to guide the choices of templates;and (2) a generalised Farkas' lemma in terms of observables (Hermitian operators) in quantum physics.
作者:
Ying, MingshengFeng, YuanUniv Technol Sydney
Fac Engn & Informat Technol Ctr Quantum Computat & Intelligent Syst Sydney NSW 2007 Australia Tsinghua Univ
Dept Comp Sci & Technol Tsinghua Natl Lab Informat Sci & Technol State Key Lab Intelligent Technol & Syst Beijing 100084 Peoples R China
Several high-level quantum programming languages have been proposed in the previous research. In this paper, we define a low-level flowchart language for quantum programming, which can be used in implementation of hig...
详细信息
Several high-level quantum programming languages have been proposed in the previous research. In this paper, we define a low-level flowchart language for quantum programming, which can be used in implementation of high-level quantum languages and in design of quantum compilers. The formal semantics of the flowchart language is given, and the notion of correctness for programs written in this language is introduced. A structured quantum programming theorem is presented, which provides a technique of translating quantum flowchart programs into programs written in a high-level language, namely, a quantum extension of the while-language.
We present the basic high-level structures used for developing quantum programming languages. The presented structures are commonly used in many existing quantum programming languages and we use quantum pseudo-code ba...
详细信息
We present the basic high-level structures used for developing quantum programming languages. The presented structures are commonly used in many existing quantum programming languages and we use quantum pseudo-code based on QCL quantum programming language to describe them. We also present the implementation of introduced structures in GNU Octave language for scientific computing. Procedures used in the implementation are available as a package quantum-octave providing library of functions, which facilitates the simulation of quantum computing. This package allows also to incorporate high-level programming concepts into the simulation in GNU Octave and Mat lab. As such it connects features unique for higl-level quantum programming languages, with the full palette of efficient computational routines commonly available in modern scientific computing systems. To present the major features of the described package we provide the implementation of selected quantum algorithms. We also show how quantum errors can be taken into account during the simulation of quantum algorithms using quantum-octave package. This is possible thanks to the ability to operate on density matrices implemented in quantum-octave.
This paper develops verification methodology for quantum programs, and the contribution of the paper is two-fold. Sharir, Pnueli and Hart [M. Sharir, A. Pnueli, S. Hart, Verification of probabilistic programs, SIAM Jo...
详细信息
This paper develops verification methodology for quantum programs, and the contribution of the paper is two-fold. Sharir, Pnueli and Hart [M. Sharir, A. Pnueli, S. Hart, Verification of probabilistic programs, SIAM Journal of Computing 13 (1984) 292-314] presented a general method for proving properties of probabilistic programs, in which a probabilistic program is modeled by a Markov chain and an assertion on the output distribution is extended to an invariant assertion on all intermediate distributions. Their method is essentially a probabilistic generalization of the classical Floyd inductive assertion method. In this paper, we consider quantum programs modeled by quantum Markov chains which are defined by super-operators. It is shown that the Sharir-Pnueli-Hart method can be elegantly generalized to quantum programs by exploiting the Schrodinger-Heisenberg duality between quantum states and observables. In particular, a completeness theorem for the Sharir-Pnueli-Hart verification method of quantum programs is established. As indicated by the completeness theorem, the Sharir-Pnueli-Hart method is in principle effective for verifying all properties of quantum programs that can be expressed in terms of Hermitian operators (observables). But it is not feasible for many practical applications because of the complicated calculation involved in the verification. For the case of finite-dimensional state spaces, we find a method for verification of quantum programs much simpler than the Sharir-Pnueli-Hart method by employing the matrix representation of super-operators and Jordan decomposition of matrices. In particular, this method enables us to compute easily the average running time and to analyze some interesting long-run behaviors of quantum programs in a finite-dimensional state space. (C) 2013 Elsevier B.V. All rights reserved.
In this article we review the concept of quantum computing and briefly discuss the state-of-art and some actual challenges in the field of software (i.e. programming languages and algorithms) for quantum computing.
ISBN:
(纸本)9781479930579
In this article we review the concept of quantum computing and briefly discuss the state-of-art and some actual challenges in the field of software (i.e. programming languages and algorithms) for quantum computing.
In this paper we offer a programming approach to quantum computation using mixed states. Mixed-state quantum systems generalise standard (pure) quantum systems by allowing the state of the system to be a probabilistic...
详细信息
In this paper we offer a programming approach to quantum computation using mixed states. Mixed-state quantum systems generalise standard (pure) quantum systems by allowing the state of the system to be a probabilistic distribution of pure states. We build on previous work by Aharonov et al. and generalise their results from quantum circuits to probabilistic (and quantum) programs.
We argue that a realistic model for quantum computations should be general with respect to measurements, and complete with respect to the information flow between the quantum and classical worlds. We discuss two alter...
详细信息
We argue that a realistic model for quantum computations should be general with respect to measurements, and complete with respect to the information flow between the quantum and classical worlds. We discuss two alternative models for general and complete quantum computations based on probability distributions of quantum state vectors and on density matrices with classical outputs. We show that both models can be structured using a generalization of monads called arrows.
We present the SQRAM architecture for quantum computing, which is based on Knill's QRAM model. We detail a suitable instruction set, which implements a universal set of quantum gates, and demonstrate the operation...
详细信息
We present the SQRAM architecture for quantum computing, which is based on Knill's QRAM model. We detail a suitable instruction set, which implements a universal set of quantum gates, and demonstrate the operation of the SQRAM with Deutsch's quantum algorithm. The compilation of high-level quantum programs for the SQRAM machine is considered;we present templates for quantum assembly code and a method for decomposing matrices for complex quantum operations. The SQRAM simulator and compiler are discussed, along with directions for future work.
暂无评论