Quantum loop programs

UTSePress Research/Manakin Repository

Search UTSePress Research

Advanced Search


My Account

Show simple item record

dc.contributor.author Ying, Mingsheng en_US
dc.contributor.author Feng, Yuan en_US
dc.contributor.editor en_US
dc.date.accessioned 2011-02-07T06:21:56Z
dc.date.available 2011-02-07T06:21:56Z
dc.date.issued 2010 en_US
dc.identifier 2009007369 en_US
dc.identifier.citation Ying Mingsheng and Feng Yuan 2010, 'Quantum loop programs', Springer-Verlag, vol. 47, no. 4, pp. 221-250. en_US
dc.identifier.issn 0001-5903 en_US
dc.identifier.other C1 en_US
dc.identifier.uri http://hdl.handle.net/10453/13461
dc.description.abstract Loop is a powerful program construct in classical computation, but its power is still not exploited fully in quantum computation. The exploitation of such power definitely requires a deep understanding of the mechanism of quantum loop programs. In this paper, we introduce a general scheme of quantum loops and describe its computational process. The function computed by a quantum loop is defined, and a denotational semantics and a weakest precondition semantics of a quantum loop are given. The notions of termination and almost termination are proposed for quantum loops. This paper only consider the case of finite-dimensional state spaces. Necessary and sufficient conditions for termination and almost termination of a general quantum loop on any mixed input state are presented. A quantum loop is said to be (almost) terminating if it (almost) terminates on any input state. We show that a quantum loop is almost terminating if and only if it is uniformly almost terminating. It is observed that a small disturbance either on the unitary transformation in the loop body or on the measurement in the loop guard can make any quantum loop (almost) terminating, provided that some dimension restriction is satisfied. Moreover, a representation of the function computed by a quantum loop is given in terms of finite summations of matrices. To illustrate the notions and results obtained in this paper, two simple classes of quantum loop programs, one qubit quantum loops, and two qubit quantum loops defined by controlled gates, are carefully examined, and to show their expressive power, quantum loops are applied in describing quantum walks. en_US
dc.language en_US
dc.publisher Springer-Verlag en_US
dc.relation.hasversion Accepted manuscript version
dc.relation.isbasedon http://dx.doi.org/10.1007/s00236-010-0117-4 en_US
dc.title Quantum loop programs en_US
dc.parent Acta Informatica en_US
dc.journal.volume 47 en_US
dc.journal.number 4 en_US
dc.publocation New York, USA en_US
dc.identifier.startpage 221 en_US
dc.identifier.endpage 250 en_US
dc.cauo.name FEIT.Faculty of Engineering & Information Technology en_US
dc.conference Verified OK en_US
dc.for 080300 en_US
dc.personcode 103396 en_US
dc.personcode 106439 en_US
dc.percentage 100 en_US
dc.classification.name Computer Software en_US
dc.classification.type FOR-08 en_US
dc.edition en_US
dc.custom en_US
dc.date.activity en_US
dc.location.activity en_US
dc.description.keywords NA en_US
dc.staffid 106439 en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record