Nondeterminism can be causal

Edward J. Gillis

Signal causality, the prohibition of superluminal information transmission, is the fundamental property shared by quantum measurement theory and relativity, and it is the key to understanding the connection between nonlocal measurement effects and elementary interactions. To prevent those effects from transmitting information between the generating and observing process, they must be induced by the kinds of entangling interactions that constitute measurements, as implied in the Projection Postulate. They must also be nondeterministic as reflected in the Born Probability Rule. The nondeterminism of entanglement-generating processes explains why the relevant types of information cannot be instantiated in elementary systems, and why the sequencing of nonlocal effects is, in principle, unobservable. This perspective suggests a simple hypothesis about nonlocal transfers of amplitude during entangling interactions, which yields straightforward experimental consequences.

Léon Brillouin

Prakash Panangaden

Emanuel H. Knill

Does the notion of a quantum randomized or nondeterministic algorithm make sense, and if so, does quantum randomness or nondeterminism add power? Although reasonable quantum random sources do not add computational power, the discussion of quantum randomness naturally leads to several definitions of the complexity of quantum states. Unlike classical string complexity, both deterministic and nondeterministic quantum state complexities are interesting. A notion of \emph{total quantum nondeterminism} is introduced for decision problems. This notion may be a proper extension of classical nondeterminism.

Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita +1 more

In this paper we study quantum nondeterminism in multiparty communication. There are three (possibly) different types of nondeterminism in quantum computation: i) strong, ii) weak with classical proofs, and iii) weak with quantum proofs. Here we focus on the first one. A strong quantum nondeterministic protocol accepts a correct input with positive probability and rejects an incorrect input with probability 1. In this work we relate strong quantum nondeterministic multiparty communication complexity to the rank of the communication tensor in the Number-On-Forehead and Number-In-Hand models. In particular, by extending the definition proposed by de Wolf to nondeterministic tensor-rank (nrank), we show that for any boolean function f when there is no prior shared entanglement between the players, 1) in the Number-On-Forehead model the cost is upper-bounded by the logarithm of nrank(f); 2) in the Number-In-Hand model the cost is lower-bounded by the logarithm of nrank(f). Furthermore, we show that when the number of players is o(log log n), we have $NQP\nsubseteq BQP$ for Number-On-Forehead communication.

Giacomo Andreoletti, Louis Vervoort