|
related topics |
{state, algorithm, problem} |
{let, theorem, proof} |
{algorithm, log, probability} |
{qubit, qubits, gate} |
{phase, path, phys} |
|
Adiabatic Quantum State Generation and Statistical Zero Knowledge
Dorit Aharonov, Amnon Ta-Shma
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.
- oai_identifier:
- oai:arXiv.org:quant-ph/0301023
- categories:
- quant-ph
- comments:
- 35 pages, two figures
- arxiv_id:
- quant-ph/0301023
- created:
- 2003-01-07
- updated:
- 2003-01-07
Full article ▸
|
|
related documents |
0212094v2 |
0504101v1 |
0601116v1 |
0001106v1 |
0405168v2 |
9802043v1 |
0308060v1 |
0605244v3 |
0611140v3 |
0506270v2 |
0702007v2 |
0411194v2 |
0312083v1 |
0609125v1 |
0303070v1 |
0502014v2 |
0405157v2 |
0510179v1 |
0506244v2 |
0401053v1 |
0610235v2 |
0405081v1 |
0503159v2 |
0605090v1 |
0410229v1 |
|