dorsal/arxiv
View SchemaNew quantum algorithm for studying NP-complete problems
| Authors | Masanori Ohya, Igor V. Volovich |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0406216 |
| URL | https://arxiv.org/abs/quant-ph/0406216 |
| DOI | 10.1016/S0034-4877(03)90002-4 |
| Journal | Rep.Math.Phys.,52, No.1,25-33, 2003 |
Abstract
Ordinary approach to quantum algorithm is based on quantum Turing machine or quantum circuits. It is known that this approach is not powerful enough to solve NP-complete problems. In this paper we study a new approach to quantum algorithm which is a combination of the ordinary quantum algorithm with a chaotic dynamical system. We consider the satisfiability problem as an example of NP-complete problems and argue that the problem, in principle, can be solved in polynomial time by using our new quantum algorithm.
{
"annotation_id": "1ca07e51-6a12-4cd2-ad24-2a318c3df3d2",
"date_created": "2026-03-02T18:02:10.386000Z",
"date_modified": "2026-03-02T18:02:10.386000Z",
"file_hash": "7aa7498a38a83ca704896751e0900a96df3afa33103362c0a88ff8d2e28af35b",
"private": false,
"record": {
"abstract": "Ordinary approach to quantum algorithm is based on quantum Turing machine or\nquantum circuits. It is known that this approach is not powerful enough to\nsolve NP-complete problems. In this paper we study a new approach to quantum\nalgorithm which is a combination of the ordinary quantum algorithm with a\nchaotic dynamical system. We consider the satisfiability problem as an example\nof NP-complete problems and argue that the problem, in principle, can be solved\nin polynomial time by using our new quantum algorithm.",
"arxiv_id": "quant-ph/0406216",
"authors": [
"Masanori Ohya",
"Igor V. Volovich"
],
"categories": [
"quant-ph"
],
"doi": "10.1016/S0034-4877(03)90002-4",
"journal_ref": "Rep.Math.Phys.,52, No.1,25-33, 2003",
"title": "New quantum algorithm for studying NP-complete problems",
"url": "https://arxiv.org/abs/quant-ph/0406216"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b56faf60-dc47-4626-b5b6-6e42abd76da2",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}