In close analogy to the fundamental role of random numbers in classical information theory, random operators are a basic component of quantum information theory. Unfortunately, the implementation of random unitary operators on a quantum processor is exponentially hard. Here we introduce a method for generating pseudo-random unitary operators that can reproduce those statistical properties of random unitary operators most relevant to quantum information tasks. This method requires exponentially fewer resources, and hence enables the practical application of random unitary operators in quantum communication and information processing protocols. Using a nuclear magnetic resonance quantum processor, we were able to realize pseudorandom unitary operators that reproduce the expected random distribution of matrix elements.
Physical sources of randomness are indispensable for information technology and cryptography. Yet, the usefulness of random processes seems to be ignored by many natural science researchers, who are exposed to the downsides of randomness, which adds noise and uncertainty to experiments. Here, we look at experimental science through the lens of information theory, with entropy as a key concept that bridges multiple fields. By examining physical unclonable functions and molecular information technology, we highlight interdisciplinary research leveraging these synergies. With this perspective, we hope to inspire the fascination of randomness and entropy in science, encouraging new research directions across different disciplines. Physical sources of randomness are indispensable for information technology and modern cryptography. In this Perspective, the authors explore entropy as a key concept and the interdisciplinary work that utilizes randomness.
We study approximating multivariate functions from a reproducing kernel Hilbert space with the error between the function and its approximation measured in a weighted
L2-norm. We consider functions with an arbitrarily large number of variables,
d, and we focus on the randomized setting with algorithms using standard information consisting of function values at randomly chosen points. We prove that standard information in the randomized setting is as powerful as linear information in the worst case setting. Linear information means that algorithms may use arbitrary continuous linear functionals, and by the power of information we mean the speed of convergence of the
nth minimal errors, i.e., of the minimal errors among all algorithms using
n function evaluations. Previously, it was only known that standard information in the randomized setting is no more powerful than the linear information in the worst case setting. We also study (strong) tractability of multivariate approximation in the randomized setting. That is, we study when the minimal number of function evaluations needed to reduce the initial error by a factor
ε is polynomial in
ε−1 (strong tractability), and polynomial in
d and
ε−1 (tractability). We prove that these notions in the randomized setting for standard information are equivalent to the same notions in the worst case setting for linear information. This result is useful since for a number of important applications only standard information can be used and verifying (strong) tractability for standard information is in general difficult, whereas (strong) tractability in the worst case setting for linear information is known for many spaces and is relatively easy to check. We illustrate the tractability results for weighted Korobov spaces. In particular, we present necessary and sufficient conditions for strong tractability and tractability. For product weights independent of
d, we prove that strong tractability is equivalent to tractability. We stress that all proofs are constructive. That is, we provide randomized algorithms that enjoy the maximal speed of convergence. We also exhibit randomized algorithms which achieve strong tractability and tractability error bounds.