Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Computing in Science & Engineering

Computational complexity for physicists

Stephan Mertens

Published Jan 1, 2002• 63 citations
Publisher

Abstract

The theory of computational complexity has some interesting links to physics, in particular to quantum computing and statistical mechanics. The article contains an informal introduction to this theory and its links to physics.
DOI
10.1109/5992.998639

Related papers

Computational Complexity for Physicists

Stephan Mertens

These lecture notes are an informal introduction to the theory of computational complexity and its links to quantum computing and statistical mechanics.

arXiv:cond-mat/0012185•Dec 11, 2000•6 citations

A Short Introduction to Quantum Computing for Physicists

Oswaldo Zapata

These notes provide an introduction to standard topics on quantum computation and communication for those who already have a basic knowledge of quantum mechanics. The main target audience are professional physicists as well as advanced students of physics; however, engineers and computer scientists may also benefit from them.

arXiv:2306.09388•Jun 15, 2023•2 citations

Hugh Everett handwritten draft letter to E.T. Jaynes, 15-May-1957

Hugh Everett

One of the most successful physicists of the generation immediately before Hugh Everett III, E. T. Jaynes shared both Everett's interest in applications of information theory to physics and his foundational orientation. But whereas Everett focused on quantum mechanics, much of Jaynes' work concerned how to use information theory in thermodynamics. Here Everett sketches an initial reaction to a published paper of Jaynes', Information Theory and Statistical Mechanics, Physical Review, 106, 620-630 (1957). The date on the document corresponds to the date that Jaynes' article appeared in print, and not necessarily to the date on which the notes were written.

•May 19, 2011•0 citations

Aspects Of Computability In Physics

Joseph Shipman

This paper reviews connections between physics and computation, and explores their implications. The main topics are computational "hardness" of physical systems, computational status of fundamental theories, quantum computation, and the Universe as a computer.

arXiv:math/9711204•Workshop on Physics and Computation (PhysComp)•Aug 24, 2005•4 citations

One Complexity Theorist's View of Quantum Computing

Lance Fortnow

The complexity of quantum computation remains poorly understood. While physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or the other as to how useful these machines will be. The tools of computational complexity theory should come to bear on these important questions. Quantum computing often scares away many potential researchers from computer science because of the apparent background need in quantum mechanics and the alien looking notation used in papers on the topic. This paper will give an overview of quantum computation from the point of view of a complexity theorist. We will see that one can think of BQP as yet another complexity class and study its power without focusing on the physical aspects behind it.

arXiv:quant-ph/0003035•Mar 9, 2000•2 citations

Integration in Functional Spaces and its Applications in Quantum Physics

Izrail Moiseevich Gelfand, Akiva M. Yaglom

This translation of the survey article by I. M. Gel'fand and A. M. Yaglom on the theory and applications of integration in functional spaces in problems of quantum physics was prepared because it was felt that such a review would be of interest and of use to mathematical physicists working in several different fields. The article begins with a discussion of Wiener measure, after which the extension is made to the complex measure introduced by Feynman in his formulation of quantum mechanics, and examples are given of the use of these methods in quantum mechanics, quantum field theory, and quantum statistical physics. A comprehensive bibliography of works devoted to the theory and applications of functional integration methods is included.

Journal of Mathematical Physics•Jan 1, 1960•690 citations
One of the most successful physicists of the generation immediately before Hugh Everett III, E. T. Jaynes shared both Everett's interest in applications of information theory to physics and his foundational orientation. But whereas Everett focused on quantum mechanics, much of Jaynes' work concerned how to use information theory in thermodynamics. Here Everett sketches an initial reaction to a published paper of Jaynes', Information Theory and Statistical Mechanics, Physical Review, 106, 620-630 (1957). The date on the document corresponds to the date that Jaynes' article appeared in print, and not necessarily to the date on which the notes were written.
The complexity of quantum computation remains poorly understood. While physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or the other as to how useful these machines will be. The tools of computational complexity theory should come to bear on these important questions. Quantum computing often scares away many potential researchers from computer science because of the apparent background need in quantum mechanics and the alien looking notation used in papers on the topic. This paper will give an overview of quantum computation from the point of view of a complexity theorist. We will see that one can think of BQP as yet another complexity class and study its power without focusing on the physical aspects behind it.
This translation of the survey article by I. M. Gel'fand and A. M. Yaglom on the theory and applications of integration in functional spaces in problems of quantum physics was prepared because it was felt that such a review would be of interest and of use to mathematical physicists working in several different fields. The article begins with a discussion of Wiener measure, after which the extension is made to the complex measure introduced by Feynman in his formulation of quantum mechanics, and examples are given of the use of these methods in quantum mechanics, quantum field theory, and quantum statistical physics. A comprehensive bibliography of works devoted to the theory and applications of functional integration methods is included.