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

Springer eBooks

Complexity Theory

Jack D. Hidary

Published Jan 1, 2019• 2 citations
Publisher
DOI
10.1007/978-3-030-23922-0_4

Related papers

Strict advantage of complex quantum theory in a communication task

Anonymous

Standard formulations of quantum theory are based on complex numbers: Quantum states can be in superpositions, with weights given by complex probability amplitudes. Motivated by quantum theory promising a range of practical advantages over classical for a multitude of tasks, we investigate how the presence of complex amplitudes in quantum theory can yield operational advantages over counterpart real formulations. We identify a straightforward communication task for which complex quantum theory exhibits a provably lower communication cost than not just any classical approach, but also any approach based on real quantum theory. We certify the necessity of complex quantum theory for optimal approaches to the task through geometric properties of quantum state ensembles that witness the presence of basis-independent complexity. This substantiates a strict operational advantage of complex quantum theory. We discuss the relevance of this finding for quantum advantages in stochastic simulation.

arXiv:2505.16523•Physical Review A•May 19, 2025•7 citations

Algorithmic Complexity

Fabio Benatti

Theoretical and mathematical physics•Jan 1, 2009•2 citations

New barriers in complexity theory: On the solvability complexity index and the towers of algorithms

Jonathan Ben‐Artzi, Anders C. Hansen, Olavi Nevanlinna +1 more

We report on new barriers in the theory of computations. These barriers show that the standard theory of computations and complexity theory is insufficient for many core problems in computational theory. Thus we are in need for a new extended complexity theory. The new theory settles the long-standing computational spectral problem and also provides new fundamental algorithms for quantum mechanics.

Comptes Rendus Mathématique•Oct 1, 2015•33 citations

Information and Complexity Theory

Osama M. Raisuddin, Suvranu De

Springer eBooks•Nov 14, 2025•0 citations

Complex field formulation of quantum estimation theory

M. Muñoz, L. Pereira, C Vargas +2 more

Abstract We present a complex-field formulation of quantum estimation theory that natively operates with complex statistics for the dependence of complex parameters. This formulation states new complex versions of the main quantities and results of the estimation theory depending on complex parameters, such as Fisher information matrices and Cramér–Rao bounds. This can be useful in contexts where quantum states are described by complex parameters, such as coherent or squeezed states. We present an example of our theory’s application to quantum communication with coherent states.

arXiv:2203.03064•Physica Scripta•Jul 21, 2026•4 citations

Relative Complexity

Leonard Susskind

SpringerBriefs in physics•Jan 1, 2020•0 citations
Standard formulations of quantum theory are based on complex numbers: Quantum states can be in superpositions, with weights given by complex probability amplitudes. Motivated by quantum theory promising a range of practical advantages over classical for a multitude of tasks, we investigate how the presence of complex amplitudes in quantum theory can yield operational advantages over counterpart real formulations. We identify a straightforward communication task for which complex quantum theory exhibits a provably lower communication cost than not just any classical approach, but also any approach based on real quantum theory. We certify the necessity of complex quantum theory for optimal approaches to the task through geometric properties of quantum state ensembles that witness the presence of basis-independent complexity. This substantiates a strict operational advantage of complex quantum theory. We discuss the relevance of this finding for quantum advantages in stochastic simulation.
Abstract We present a complex-field formulation of quantum estimation theory that natively operates with complex statistics for the dependence of complex parameters. This formulation states new complex versions of the main quantities and results of the estimation theory depending on complex parameters, such as Fisher information matrices and Cramér–Rao bounds. This can be useful in contexts where quantum states are described by complex parameters, such as coherent or squeezed states. We present an example of our theory’s application to quantum communication with coherent states.