Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Springer eBooks

On the Ohya-Masuda Quantum SAT Algorithm

Luigi Accardi, Ruben Sabbadini

Published Jan 1, 2001• 22 citations
Publisher
DOI
10.1007/978-1-4471-0313-4_1

Related papers

Assessing the Viability of Quantum SAT Solvers: A Comparative Study Using Grover’s Algorithm and Quantum Hardware

Marcos Alemany Manzanaro, Higinio Mora

Lecture notes in networks and systems•Oct 28, 2025•2 citations

A Note on the Ohya-Masuda Quantum Algorithm

M. Dugić

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.

Open Systems & Information Dynamics•Jun 1, 2002•1 citation

Quantum Hybrid Algorithm for Solving SAT Problem

Charles Varmantchaonala Moudina, Jean Louis Ebongue Kedieng Fendji, J.-P. Tchapet Njafa +1 more

Engineering Applications of Artificial Intelligence•Jan 1, 2022•8 citations

Three “quantum” algorithms to solve 3-SAT

Alberto Leporati, Sara Felloni

Theoretical Computer Science•Dec 1, 2006•18 citations

Estimation of Complexity for the Ohya-Masuda-Volovich SAT Algorithm

Shigeo Akashi, Satoshi Iriyama

Ohya and Volovich have been proposed a new quantum computation model with chaos amplification to solve the SAT problem, which went beyond usual quantum algorithm. In this paper we study the complexity of the SAT algorithm by counting the steps of computation algorithm rigorously, which was mentioned in the paper [1,2,3,5,7]For this purpose, we refine the quantum gates treating the SAT problem step by step.

arXiv:quant-ph/0312074•Dec 9, 2003•1 citation

Quantum cooperative search algorithm for 3-SAT

Sheng-Tzong Cheng, Ming‐Hung Tao

Journal of Computer and System Sciences•Oct 20, 2006•17 citations
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.