Complexity Theory

Fabio Benatti

Thomas J. Elliott

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.

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.

Osama M. Raisuddin, Suvranu De

Lorenzo M. Procopio, Lee A. Rozema, Zi Jing Wong +5 more

In standard quantum mechanics, complex numbers are used to describe the wavefunction. Although complex numbers have proven sufficient to predict the results of existing experiments, there is no apparent theoretical reason to choose them over real numbers or generalizations of complex numbers, i.e. hyper-complex numbers. Experiments performed to date have proven that real numbers are insufficient, but whether or not hyper-complex numbers are required remains an open question. Quantum theories based on hyper-complex numbers are one example of a post-quantum theory, which must be put on a firm experimental foundation. Here we experimentally probe hyper-complex quantum theories, by studying one of their deviations from complex quantum theory: the non-commutativity of phases. We do so by passing single photons through a Sagnac interferometer containing two physically different phases, having refractive indices of opposite sign. By showing that the phases commute with high precision, we place limits on a particular prediction of hyper-complex quantum theories.

Kim Christensen, Nicholas R. Moloney