The human mind understands logical processes and causality and formulates theories based on logical descriptions of empirical evidence. The Principles of Causal Conspiracy is based on defining information as logical charges similar to electric charges. Such information charges can be modeled in the vacuum of a quantum probability firmament as symmetry of quantum charges with a zero net charge. Observation of a state lifts one of these charges in a Möbius transformation from a multipolar field of possibilities that maximizes a local monopole field that is observable. In the first of several papers, I introduce new and profound principles, the Principles of Causal Conspiracy, to provide a consistent epistemology for quantum theory, relativity theory and all the known sciences.
Classical programming languages cannot model essential elements of complex systems such as true random number generation. This paper develops a formal programming language called the lambda-q calculus that addresses the fundamental properties of complex systems. This formal language allows the expression of quantumized algorithms, which are extensions of randomized algorithms in that probabilities can be negative, and events can cancel out. An illustration of the power of quantumized algorithms is the ability to efficiently solve the satisfiability problem, something that many believe is beyond the capability of classical computers. This paper proves that the lambda-q calculus is not only capable of solving satisfiability but can also simulate such complex systems as quantum computers. Since satisfiability is believed to be beyond the capabilities of quantum computers, the lambda-q calculus may be strictly stronger.
There has been a body of work deriving the complex Hilbert-space structure of quantum theory from axioms/principles/postulates to deepen our understanding of quantum theory and to reveal ways to go beyond it to resolve foundational issues. Recent progress in incorporating indefinite causal structure into physical theories suggests that a more comprehensive understanding of both quantum theory and the theory beyond it accounts for indefinite causal structure. We formulate a framework of physical theories without assuming definite causal structure and identify postulates that single out the complex Hilbert-space structure. More than one complex Hilbert-space theory is compatible with the postulates, which leaves room for further search for the best among these theories.
Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice. We initiate a systematic study of its quantum counterpart and show the following results.
(1) We show that there is a total function whose smoothed quantum query complexity is exponentially smaller than its classical query complexity.
(2) We give near-tight characterizations of smoothed randomized and quantum query complexities for symmetric Boolean functions, unifying the worst-case complexity results of [Beals et al, FOCS'98] and average-case complexity results of [Ambainis and de Wolf, STACS'00].
(3) We study string problems such as pattern matching and edit distance and, in various regimes, give polynomial to superpolynomial quantum speedups. Our main technical ingredients include a near-tight quantum algorithm for
ε-approximating the number of collisions between two non-repetitive strings, improving the result of Le Gall and Ng [QIC'22]. Together, our results show that smoothing can reveal larger quantum speedups than worst-case analysis suggests, opening a path towards quantum advantage on more realistic inputs.