dorsal/arxiv
View SchemaThe lambda-q calculus can efficiently simulate quantum computers
| Authors | Philip Maymin |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9702057 |
| URL | https://arxiv.org/abs/quant-ph/9702057 |
Abstract
We show that the lambda-q calculus can efficiently simulate quantum Turing machines by showing how the lambda-q calculus can efficiently simulate a class of quantum cellular automaton that are equivalent to quantum Turing machines. We conclude by noting that the lambda-q calculus may be strictly stronger than quantum computers because NP-complete problems such as satisfiability are efficiently solvable in the lambda-q calculus but there is a widespread doubt that they are efficiently solvable by quantum computers.
{
"annotation_id": "8f200e16-e3cc-4c3e-83df-b8ef9bfcc2ba",
"date_created": "2026-03-02T18:02:40.452000Z",
"date_modified": "2026-03-02T18:02:40.452000Z",
"file_hash": "ec409e4281edeeb3ee1548eb80e1700d26244b2b2bc1ab2d405022a02cf927f5",
"private": false,
"record": {
"abstract": "We show that the lambda-q calculus can efficiently simulate quantum Turing\nmachines by showing how the lambda-q calculus can efficiently simulate a class\nof quantum cellular automaton that are equivalent to quantum Turing machines.\nWe conclude by noting that the lambda-q calculus may be strictly stronger than\nquantum computers because NP-complete problems such as satisfiability are\nefficiently solvable in the lambda-q calculus but there is a widespread doubt\nthat they are efficiently solvable by quantum computers.",
"arxiv_id": "quant-ph/9702057",
"authors": [
"Philip Maymin"
],
"categories": [
"quant-ph"
],
"title": "The lambda-q calculus can efficiently simulate quantum computers",
"url": "https://arxiv.org/abs/quant-ph/9702057"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "90c6727e-89c6-44de-b868-5b3871dc9981",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}