期刊
SIAM JOURNAL ON COMPUTING
卷 37, 期 1, 页码 47-82出版社
SIAM PUBLICATIONS
DOI: 10.1137/060648829
关键词
quantum computation; quantum algorithm; adiabatic theorem; Hamiltonians; Markov chains; quantum sampling; state generation; statistical zero knowledge; Zeno effect; spectral gap
The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to this task by studying the problem of quantum state generation. We motivate this problem by showing that the entire class of statistical zero knowledge, which contains natural candidates for efficient quantum algorithms such as graph isomorphism and lattice problems, can be reduced to the problem of quantum state generation. To study quantum state generation, we de. ne a paradigm which we call adiabatic state generation (ASG) and which is based on adiabatic quantum computation. The ASG paradigm is not meant to replace the standard quantum circuit model or to improve on it in terms of computational complexity. Rather, our goal is to provide a natural theoretical framework, in which quantum state generation algorithms could be designed. The new paradigm seems interesting due to its intriguing links to a variety of different areas: the analysis of spectral gaps and ground-states of Hamiltonians in physics, rapidly mixing Markov chains, adiabatic computation, and approximate counting. To initiate the study of ASG, we prove several general lemmas that can serve as tools when using this paradigm. We demonstrate the application of the paradigm by using it to turn a variety of ( classical) approximate counting algorithms into efficient quantum state generators of nontrivial quantum states, including, for example, the uniform superposition over all perfect matchings in a bipartite graph.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据