dorsal/arxiv
View SchemaSimulation of finite state machines in a quantum computer
| Authors | M. R. Dunlavey |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9807026 |
| URL | https://arxiv.org/abs/quant-ph/9807026 |
Abstract
A construction is given for simulating any deterministic finite state machine (FSM) on a quantum computer in a space-efficient manner. By constructing a superposition of input strings of lengths K or less, questions can be asked about the FSM, such as the inputs that reach particular nodes, and the answers can be found using a search algorithm such as Grover's. This has implications for the eventual utility of quantum computers for software validation.
{
"annotation_id": "f841d9ae-7839-45cb-8aa7-e0b42dd9448d",
"date_created": "2026-03-02T18:02:44.351000Z",
"date_modified": "2026-03-02T18:02:44.351000Z",
"file_hash": "10a13963891f5d822905075f958057de9b7e869e18cd0e4e3da1fcac26d0d10b",
"private": false,
"record": {
"abstract": "A construction is given for simulating any deterministic finite state machine\n(FSM) on a quantum computer in a space-efficient manner. By constructing a\nsuperposition of input strings of lengths K or less, questions can be asked\nabout the FSM, such as the inputs that reach particular nodes, and the answers\ncan be found using a search algorithm such as Grover\u0027s. This has implications\nfor the eventual utility of quantum computers for software validation.",
"arxiv_id": "quant-ph/9807026",
"authors": [
"M. R. Dunlavey"
],
"categories": [
"quant-ph"
],
"title": "Simulation of finite state machines in a quantum computer",
"url": "https://arxiv.org/abs/quant-ph/9807026"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "245ad24f-dbb0-4918-8a5d-936f3c0c0334",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}