dorsal/arxiv
View SchemaImplementation for Solving Random Satisfiability Problems through CNOT-based circuits in a NMR Quantum Processor
| Authors | Xinhua Peng, Xiwen Zhu, Kelin Gao |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0308130 |
| URL | https://arxiv.org/abs/quant-ph/0308130 |
Abstract
We give a general method of construting quantum circuit for random \QTR{it}{satisfiability} (SAT) problems with the basic logic gates such as multi-qubit controlled-NOT and NOT gates. The sizes of these circuits are almost the same as the sizes of the SAT formulas. Further, a parallelization scheme is described to solve random SAT problems efficiently through these quantum circuits in \QTR{it}{nuclear magnetic resonance} (NMR) ensemble quantum computing. This scheme exploits truly mixed states as input states rather than pseudo-pure states, and combines with the topological nanture of the NMR spectrum to identify the solutions to SAT problems in a parallel way. Several typical SAT problems have been experimentally demonstrated by this scheme with good performances.
{
"annotation_id": "c30a2171-f508-40fd-997a-1580afef5ba0",
"date_created": "2026-03-02T18:02:02.268000Z",
"date_modified": "2026-03-02T18:02:02.268000Z",
"file_hash": "7619a79ccac135841080f93e0ea66afe401d49dae7bae1206b35b4bbd902afaa",
"private": false,
"record": {
"abstract": "We give a general method of construting quantum circuit for random\n\\QTR{it}{satisfiability} (SAT) problems with the basic logic gates such as\nmulti-qubit controlled-NOT and NOT gates. The sizes of these circuits are\nalmost the same as the sizes of the SAT formulas. Further, a parallelization\nscheme is described to solve random SAT problems efficiently through these\nquantum circuits in \\QTR{it}{nuclear magnetic resonance} (NMR) ensemble quantum\ncomputing. This scheme exploits truly mixed states as input states rather than\npseudo-pure states, and combines with the topological nanture of the NMR\nspectrum to identify the solutions to SAT problems in a parallel way. Several\ntypical SAT problems have been experimentally demonstrated by this scheme with\ngood performances.",
"arxiv_id": "quant-ph/0308130",
"authors": [
"Xinhua Peng",
"Xiwen Zhu",
"Kelin Gao"
],
"categories": [
"quant-ph"
],
"title": "Implementation for Solving Random Satisfiability Problems through CNOT-based circuits in a NMR Quantum Processor",
"url": "https://arxiv.org/abs/quant-ph/0308130"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "e2bacfbb-421e-4d90-954c-b500487ad639",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}