ﻻ يوجد ملخص باللغة العربية
Randomness plays a central rol in the quantum mechanical description of our interactions. We review the relationship between the violation of Bell inequalities, non signaling and randomness. We discuss the challenge in defining a random string, and show that algorithmic information theory provides a necessary condition for randomness using Borel normality. We close with a view on incomputablity and its implications in physics.
Quantum information processing shows advantages in many tasks, including quantum communication and computation, comparing to its classical counterpart. The essence of quantum processing lies on the fundamental difference between classical and quantum
Algorithmic randomness theory starts with a notion of an individual random object. To be reasonable, this notion should have some natural properties; in particular, an object should be random with respect to image distribution if and only if it has a
Many constructions in computability theory rely on time tricks. In the higher setting, relativising to some oracles shows the necessity of these. We construct an oracle~$A$ and a set~$X$, higher Turing reducible to~$X$, but for which $Psi(A) e X$ for
We consider a new model for the testing of untrusted quantum devices, consisting of a single polynomial-time bounded quantum device interacting with a classical polynomial-time verifier. In this model we propose solutions to two tasks - a protocol fo
In this paper we investigate algorithmic randomness on more general spaces than the Cantor space, namely computable metric spaces. To do this, we first develop a unified framework allowing computations with probability measures. We show that any comp