On the difficulty of computations

Gregory J. Chaitin

Brielin C. Brown, Steven T. Flammia, Norbert Schuch

We study the computational difficulty of computing the ground state degeneracy and the density of states for local Hamiltonians. We show that the difficulty of both problems is exactly captured by a class which we call #BQP, which is the counting version of the quantum complexity class quantum Merlin Arthur. We show that #BQP is not harder than its classical counting counterpart #P, which in turn implies that computing the ground state degeneracy or the density of states for classical Hamiltonians is just as hard as it is for quantum Hamiltonians.

Sven Laur, Helger Lipmaa

Douglas Snyder

Issues related to a materialist philosophy are explored as concerns the implied equivalence of computers running software and human observers. One issue explored concerns the measurement process in quantum mechanics. Another issue explored concerns the nature of experience as revealed by the existence of dreams. Some difficulties stemming from a materialist philosophy as regards these issues are pointed out. For example, a gedankenexperiment involving what has been called "negative" observation is discussed that illustrates the difficulty with a materialist assumption in quantum mechanics. Based on an exploration of these difficulties, specifications are outlined briefly that would provide a means to demonstrate the equivalence of of computers running software and human experience given a materialist assumption.

A. Kitaev, Alexander Khanievich Shen', M. Vyalyi

Seiseki Akibue, Yuki Takeuchi, Yasuhiro Takahashi +2 more

To develop large-scale fault-tolerant quantum computers, implementation technologies are required to meet extremely strict conditions.Basic research targeting such technologies is currently being conducted worldwide, and theoretical research can also make a relevant contribution.In this article, we introduce several theoretical research studies for deriving the maximum power of quantum computers with limited resources and/or restricted functions due to difficulties in physical implementation.