A Note on the Ohya-Masuda Quantum Algorithm

Author: Dugi cacute M.

Source: Open Systems and Information Dynamics, Volume 9, Number 2, 2002 , pp. 115-123(9)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

We analyze the Ohya-Masuda quantum algorithm that solves the so-called “satisfiability” problem, which is an NP-complete problem of the complexity theory. We distinguish three steps in the algorithm, and analyze the second step, in which a coherent superposition of states (a “pure” state) transforms into an “incoherent” mixture presented by a density matrix. We show that, if “nonideal” (in analogy with “nonideal” quantum measurement), this transformation can make the algorithm to fail in some cases. On this basis we give some general notions on the physical implementation of the Ohya-Masuda algorithm.

Language: English

Document Type: Regular paper

Affiliations: 1: Department of Physics, Faculty of Science P.O. Box 60, 34 000 Kragujevac, Yugoslavia

Publication date: 2002-01-01