Quantum Foundations

Query complexity is a common tool for comparing quantum and classical computation, and it has produced many examples of how quantum algorithms differ from classical ones. Here we investigate in detail the role that oracles play for the advantage of quantum algorithms. We do so by using a simulation framework, Quantum Simulation Logic (QSL), to construct oracles and algorithms that solve some problems with the same success probability and number of queries as the quantum algorithms. The framework can be simulated using only classical resources at a constant overhead as compared to the quantum resources used in quantum computation. Our results clarify the assumptions made and the conditions needed when using quantum oracles. Using the same assumptions on oracles within the simulation framework we show that for some specific algorithms, such as the Deutsch-Jozsa and Simon’s algorithms, there simply is no advantage in terms of query complexity. This does not detract from the fact that quantum query complexity provides examples of how a quantum computer can be expected to behave, which in turn has proved useful for finding new quantum algorithms outside of the oracle paradigm, where the most prominent example is Shor’s algorithm for integer factorization.

Bell inequalities are important tools in contrasting classical and quantum behaviors. To date, most Bell inequalities are linear combinations of statistical correlations between remote parties. Nevertheless, finding the classical and quantum mechanical (Tsirelson) bounds for a given Bell inequality in a general scenario is a difficult task which rarely leads to closed-form solutions. Here we introduce a new class of Bell inequalities based on products of correlators that alleviate these issues. Each such Bell inequality is associated with a non-cooperative coordination game. In the simplest case, Alice and Bob, each  having two random variables, attempt to maximize the area of a rectangle and the rectangle’s area is represented by a certain parameter. This parameter, which is a function of the correlations between their random variables, is shown to be a Bell parameter, i.e. the achievable bound using only classical correlations is strictly smaller than the achievable bound using non-local quantum correlations We continue by generalizing to the case in which Alice and Bob, each having now n random variables, wish to maximize a certain volume in n-dimensional space. We term this parameter a multiplicative Bell parameter and prove its Tsirelson bound. Finally, we investigate the case of local hidden variables and show that for any deterministic strategy of one of the players the Bell parameter is a harmonic function whose maximum approaches the Tsirelson bound as the number of measurement devices increases. Some implications of these results are discussed.

The no-signalling principle, preventing superluminal communication and the consequent logical paradoxes, is typically formulated within the information-theoretic framework in terms of admissible correlations in composite systems. In my talk, I will present its complementary incarnation associated with dynamics of single systems subject to invasive measurements. The `dynamical no-signalling principle' applies to any theory with well defined rules of calculating detection statistics in spacetime. It thus offers a new framework, based on measure theory, for studying ``post-quantum'' theories in spacetime. I will show that, strikingly, the `dynamical no-signalling' principle rules out some of the well know models of quantum wave dynamics.

Randomness is a valuable resource in both classical and quantum networks and we wish to generate desired probability distributions as cheaply as possible. If we are allowed to slightly change the distribution under some tolerance level, we can sometimes greatly reduce the cardinality of the randomness or the dimension of the entanglement. By studying statistical inequalities, we show how to upper bound of the amount of randomness required for any given classical network and tolerance level. We also present a problem we encounter when compressing the randomness in a quantum network.