Equivalence checking of quantum finite-state machines
Copyright policy )Equivalence checking of quantum finite-state machines
In this paper, we introduce the model of quantum Mealy machines and study the equivalence checking and minimisation problems of them. Two efficient algorithms are developed for checking equivalence of two states in the same machine and for checking equivalence of two machines. As an application, they are used in equivalence checking of quantum circuits. Moreover, the minimisation problem is proved to be in $\textbf{PSPACE}$.
Minor corrections. 29 pages, 2 figures, 3 tables, 2 algorithms
- Chinese Academy of Sciences China (People's Republic of)
- Institute of Software China (People's Republic of)
- University of Chinese Academy of Sciences China (People's Republic of)
- State Key Laboratory of Computer Science China (People's Republic of)
- University of Technology Sydney (UTS) Australia
Mealy machines, FOS: Computer and information sciences, Quantum Physics, minimisation, Formal Languages and Automata Theory (cs.FL), FOS: Physical sciences, Computer Science - Formal Languages and Automata Theory, Formal languages and automata, quantum computing, Quantum computation, equivalence checking, quantum circuits, Quantum Physics (quant-ph)
Mealy machines, FOS: Computer and information sciences, Quantum Physics, minimisation, Formal Languages and Automata Theory (cs.FL), FOS: Physical sciences, Computer Science - Formal Languages and Automata Theory, Formal languages and automata, quantum computing, Quantum computation, equivalence checking, quantum circuits, Quantum Physics (quant-ph)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!