dorsal/arxiv
View SchemaAdiabatic Quantum State Generation and Statistical Zero Knowledge
| Authors | Dorit Aharonov, Amnon Ta-Shma |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0301023 |
| URL | https://arxiv.org/abs/quant-ph/0301023 |
Abstract
The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to the problem, by studying the problem of 'quantum state generation'. This approach provides intriguing links between many different areas: quantum computation, adiabatic evolution, analysis of spectral gaps and groundstates of Hamiltonians, rapidly mixing Markov chains, the complexity class statistical zero knowledge, quantum random walks, and more. We first show that many natural candidates for quantum algorithms can be cast as a state generation problem. We define a paradigm for state generation, called 'adiabatic state generation' and develop tools for adiabatic state generation which include methods for implementing very general Hamiltonians and ways to guarantee non negligible spectral gaps. We use our tools to prove that adiabatic state generation is equivalent to state generation in the standard quantum computing model, and finally we show how to apply our techniques to generate interesting superpositions related to Markov chains.
{
"annotation_id": "4c887aa1-f16f-4566-b73a-318ff63fe27e",
"date_created": "2026-03-02T18:01:56.182000Z",
"date_modified": "2026-03-02T18:01:56.182000Z",
"file_hash": "402df2a50c705d7a08982147cfe7255a521c4177c0ceceeec8295b95b108c116",
"private": false,
"record": {
"abstract": "The design of new quantum algorithms has proven to be an extremely difficult\ntask. This paper considers a different approach to the problem, by studying the\nproblem of \u0027quantum state generation\u0027. This approach provides intriguing links\nbetween many different areas: quantum computation, adiabatic evolution,\nanalysis of spectral gaps and groundstates of Hamiltonians, rapidly mixing\nMarkov chains, the complexity class statistical zero knowledge, quantum random\nwalks, and more.\n We first show that many natural candidates for quantum algorithms can be cast\nas a state generation problem. We define a paradigm for state generation,\ncalled \u0027adiabatic state generation\u0027 and develop tools for adiabatic state\ngeneration which include methods for implementing very general Hamiltonians and\nways to guarantee non negligible spectral gaps. We use our tools to prove that\nadiabatic state generation is equivalent to state generation in the standard\nquantum computing model, and finally we show how to apply our techniques to\ngenerate interesting superpositions related to Markov chains.",
"arxiv_id": "quant-ph/0301023",
"authors": [
"Dorit Aharonov",
"Amnon Ta-Shma"
],
"categories": [
"quant-ph"
],
"title": "Adiabatic Quantum State Generation and Statistical Zero Knowledge",
"url": "https://arxiv.org/abs/quant-ph/0301023"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "471444d0-f215-4c10-a9de-5aeca59afe6b",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}