检索结果-内蒙古大学图书馆

Reachability analysis of quantum Markov decision processes

INFORMATION AND COMPUTATION 2018年 263卷 31-51页

作者： Ying, Shenggang Ying, Mingsheng Univ Technol Sydney Fac Engn & Informat Technol Ctr Quantum Software & Informat Sydney NSW Australia Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing Peoples R China Tsinghua Univ Dept Comp Sci & Technol Beijing Peoples R China

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.

关键词： quantum programming Semantic model Markov decision process Reachability

来源：评论

学校读者我要写书评

暂无评论

quantum Hoare Logic with Classical Variables

引用

ACM TRANSACTIONS ON quantum COMPUTING 2021年第4期2卷 1-1页

作者： Feng, Yuan Ying, Mingsheng Univ Technol Sydney Sydney Australia Chinese Acad Sci Beijing Peoples R China Tsinghua Univ Beijing Peoples R China Univ Technol Sydney Ctr Quantum Software & Informat Sydney NSW Australia Chinese Acad Sci Inst Software Beijing Peoples R China

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.

关键词： quantum programming quantum while language

来源：评论

学校读者我要写书评

暂无评论

Algorithmic Analysis of Termination Problems for quantum Programs

引用

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2018年第POPL期2卷 1-29页

作者： Li, Yangjia Ying, Mingsheng Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing 100190 Peoples R China Univ Technol Sydney Sydney NSW Australia Tsinghua Univ Beijing 100084 Peoples R China

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.

关键词： quantum programming termination ranking function super-martingale SDP (Semi-Definite programming) quantum random walk quantum Bernoulli factory

来源：评论

学校读者我要写书评

暂无评论

A Flowchart Language for quantum programming

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 2011年第4期37卷 466-485页

作者： Ying, Mingsheng Feng, Yuan Univ 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 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.

关键词： quantum programming flowchart language while-language structured programming

来源：评论

学校读者我要写书评

暂无评论

Extending scientific computing system with structural quantum programming capabilities

引用

BULLETIN OF THE POLISH ACADEMY OF SCIENCES-TECHNICAL SCIENCES 2010年第1期58卷 77-88页

作者： Gawron, P. Klamka, J. Miszczak, J. A. Winiarczyk, R. Polish Acad Sci Inst Theoret & Appl Informat PL-44100 Gliwice Poland

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.

关键词： quantum information quantum programming models of quantum computation

来源：评论

学校读者我要写书评

暂无评论

t Verification of quantum programs

引用

SCIENCE OF COMPUTER programming 2013年第9期78卷 1679-1700页

作者： Ying, Mingsheng Yu, Nengkun Feng, Yuan Duan, Runyao Univ Technol Sydney Ctr Quantum Computat & Intelligent Syst QCIS Fac Engn & Informat Technol Sydney NSW 2007 Australia Tsinghua Univ Dept Comp Sci & Technol Tsinghua Natl Lab Informat Sci & Technol Beijing 100084 Peoples R China Chinese Acad Sci AMSS UTS Joint Res Lab Quantum Computat Beijing Peoples R China

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.

关键词： quantum programming Verification Sharir-Pnueli-Hart method

来源：评论

学校读者我要写书评

暂无评论

quantum Computing: State-of-art and Challenges

Quantum Computing: State-of-art and Challenges

引用

Workshop-School on Theoretical Computer Science (WEIT)

作者： Vizzotto, Juliana Kaizer CT UFSM Dept Linguagens & Sistemas Computacao Programa Posgrad Informat Santa Maria RS Brazil

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

关键词： quantum computing quantum programming quantum algorithms

来源：评论

学校读者我要写书评

暂无评论

quantum programming With Mixed States

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2007年 170卷 185-199页

作者： Zuliani, Paolo Princeton Univ Dept Comp Sci Princeton NJ 08544 USA

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.

关键词： quantum programming mixed state probabilistic computation quantum circuit

来源：评论

学校读者我要写书评

暂无评论

quantum Arrows in Haskell

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2008年第C期210卷 139-152页

作者： Vizzotto, Juliana Kaizer da Rocha Costa, Antonio Carlos Sabry, Amr Univ Fed Rio Grande do Sul Porto Alegre RS Brazil Univ Catolica Pelotas Pelotas Brazil Indiana Univ Bloomington IN 47405 USA

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.

关键词： quantum programming density matrices probabilities

来源：评论

学校读者我要写书评

暂无评论

Simulating and Compiling Code for the Sequential quantum Random Access Machine

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2007年 170卷 101-124页

作者： Nagarajan, Rajagopal Papanikolaou, Nikolaos Williams, David Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England City Univ London Sch Informat London EC1V 0HB England

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.

关键词： quantum computation quantum programming quantum simulators QRAM compilers

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：