Decomposition of quantum Markov chains and its applications

DOI10.1016/J.JCSS.2018.01.005zbMATH Open1391.68079arXiv1608.06024OpenAlexW2787337287MaRDI QIDQ1747488FDOQ1747488

Authors: Ji Guan, Yuan Feng, Mingsheng Ying 

Publication date: 8 May 2018

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Abstract: Markov chains have been widely employed as a fundamental model in the studies of probabilistic and stochastic communicating and concurrent systems. It is well-understood that decomposition techniques play a key role in reachability analysis and model-checking of Markov chains. (Discrete-time) quantum Markov chains have been introduced as a model of quantum communicating systems [1] and also a semantic model of quantum programs [2]. The BSCC (Bottom Strongly Connected Component) and stationary coherence decompositions of quantum Markov chains were introduced in [3, 4, 5]. This paper presents a new decomposition technique, namely periodic decomposition, for quantum Markov chains. We further establish a limit theorem for them. As an application, an algorithm to find a maximum dimensional noiseless subsystem of a quantum communicating system is given using decomposition techniques of quantum Markov chains.

Full work available at URL: https://arxiv.org/abs/1608.06024

Recommendations

• Reachability Probabilities of Quantum Markov Chains
• Model checking \(\omega\)-regular properties for quantum Markov chains
• Quantum Markov chains: description of hybrid systems, decidability of equivalence, and model checking linear-time properties
• Exogenous quantum Markov chains and reachability analysis
• Reachability analysis of recursive quantum Markov chains

zbMATH Keywords

irreducibilityperiodicityquantum Markov chainsnoiseless subsystemslimiting states

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Quantum stochastic calculus (81S25)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Probability and random processes.
• Title not available (Why is that?)
• On the generators of quantum dynamical semigroups
• On the existence of stationary states for quantum dynamical semigroups
• Quantum computation and quantum information. 10th anniversary edition
• QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
• Title not available (Why is that?)
• Open quantum random walks: reducibility, period, ergodic properties
• A Quantum Version of Wielandt's Inequality
• Quantum stochastic processes
• Unzerlegbare, nicht negative Matrizen
• Quantum stochastic processes. II
• The structures of state space concerning quantum dynamical semigroups
• Irreducible decompositions and stationary states of quantum channels
• Classification and decomposition of quantum Markov semigroups
• Reachability analysis of quantum Markov decision processes
• On limiting distributions of quantum Markov chains
• Reachability Probabilities of Quantum Markov Chains
• Reachability and termination analysis of concurrent quantum programs
• Irreducible and periodic positive maps
• (Un)decidable Problems about Reachability of Quantum Systems

Cited In (8)

• On expansion of quantum quadratic stochastic processes into fibrewise Markov processes defined on von Neumann algebras
• An improved algorithm for computing hitting probabilities of quantum walks
• An algebraic method to fidelity-based model checking over quantum Markov chains
• The Quantum Complexity of Markov Chain Monte Carlo
• Decoherence effects in the quantum qubit flip game using Markovian approximation
• On period, cycles and fixed points of a quantum channel
• Quantum hidden Markov models based on transition operation matrices
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces

This page was built for publication: Decomposition of quantum Markov chains and its applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1747488)