We give efficient deterministic algorithms for converting randomized query algorithms into deterministic ones. We first give an algorithm that takes as input a randomized
q-query algorithm
R with description length
N and a parameter
ε, runs in time
poly(N)⋅2O(q/ε), and returns a deterministic
O(q/ε)-query algorithm
D that
ε-approximates the acceptance probabilities of
R. These parameters are near-optimal: runtime
N+2Ω(q/ε) and query complexity
Ω(q/ε) are necessary. Next, we give algorithms for instance-optimal and online versions of the problem:
∘ Instance optimal: Construct a deterministic
qR⋆-query algorithm
D, where
qR⋆ is minimum query complexity of any deterministic algorithm that
ε-approximates
R.
∘ Online: Deterministically approximate the acceptance probability of
R for a specific input
x in time
poly(N,q,1/ε), without constructing
D in its entirety. Applying the techniques we develop for these extensions, we constructivize classic results that relate the deterministic, randomized, and quantum query complexities of boolean functions (Nisan, STOC 1989; Beals et al., FOCS 1998). This has direct implications for the Turing machine model of computation: sublinear-time algorithms for total decision problems can be efficiently derandomized and dequantized with a subexponential-time preprocessing step.
The last few years have been characterized by a tremendous development of quantum information and probability and their applications, including quantum computing, quantum cryptography, and quantum random generators. In spite of the successful development of quantum technology, its foundational basis is still not concrete and contains a few sandy and shaky slices. Quantum random generators are one of the most promising outputs of the recent quantum information revolution. Therefore, it is very important to reconsider the foundational basis of this project, starting with the notion of irreducible quantum randomness. Quantum probabilities present a powerful tool to model uncertainty. Interpretations of quantum probability and foundational meaning of its basic tools, starting with the Born rule, are among the topics which will be covered by this issue. Recently, quantum probability has started to play an important role in a few areas of research outside quantum physics—in particular, quantum probabilistic treatment of problems of theory of decision making under uncertainty. Such studies are also among the topics of this issue.
This thesis presents developments in the theory and application of quantum learning.The first two chapters fall under the head of classical shadow tomography, a randomized measurement technique which estimates a large number of expectation values effectively in parallel. In the first chapter on this topic, we extend classical shadow state tomography to the characterization of quantum channels. We prove that with a simple protocol involving randomized measurement of randomly generated input states evolved through channel, one can estimate many channel properties in parallel, with rigorous guarantees on the sample complexity required. In the next chapter, we bring together finite-depth classical shadows, derandomization, and tensor network simulation to present an algorithm for tailoring a sequence of measurements to a set of observables of interest, demonstrating the effectiveness of our technique for a number of tasks in quantum chemistry and simulation. The second part of this thesis presents a step toward applying ideas from quantum learning to quantum error correction. We investigate the use of prior information on qubit error rates in the decoding task, showing that prior information can significantly change decoder performance when a small number of qubits have high error rates. We present a protocol to learn the location of error-prone sites from decoding data in real time, and then apply this in turn to develop in situ protocol for calibration of gates while processing logical information.
In the last two chapters, we talked about computational complexity up till the early 1970s. Here, we'll add a new ingredient to our already simmering stew – something that was thrown in around the mid-1970s, and that now pervades complexity to such an extent that it's hard to imagine doing anything without it. This new ingredient is randomness . Certainly, if you want to study quantum computing, then you first have to understand randomized computing. I mean, quantum amplitudes only become interesting when they exhibit some behavior that classical probabilities don't : contextuality, interference, entanglement (as opposed to correlation), etc. So we can't even begin to discuss quantum mechanics without first knowing what it is that we're comparing against. Alright, so what is randomness? Well, that’s a profound philosophical question, but I’m a simpleminded person. So, you’ve got some probability p , which is a real number in the unit interval [0, 1]. That’s randomness. But wasn’t it a big achievement when Kolmogorov put probability on an axiomatic basis in the 1930s? Yes, it was! But in this chapter, we’ll only care about probability distributions over finitely many events, so all the subtle questions of integrability, measurability, and so on won’t arise. In my view, probability theory is yet another example where mathematicians immediately go to infinite-dimensional spaces, in order to solve the problem of having a nontrivial problem to solve! And that’s fine – whatever floats your boat. I’m not criticizing that. But in theoretical computer science, we’ve already got our hands full with 2n choices. We need 2ℵ0 choices like we need a hole in the head.
Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an
n×n matrix A. The algorithm runs in
O(n2/ε2) time, and approximates
Per(A) to within
±ε∥A∥n additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. \ This makes it highly relevant to quantum optics, where the permanents of bounded-norm complex matrices play a central role. (In particular,
n×n permanents arise as the transition amplitudes for
n identical photons.) Indeed, the existence of Gurvits's algorithm is why, in their recent work on the \textit{hardness} of quantum optics, Aaronson and Arkhipov (AA) had to talk about sampling problems rather than ordinary decision problems. In this paper, we improve Gurvits's algorithm in two ways. First, using an idea from quantum optics, we generalize the algorithm so that it yields a better approximation when the matrix A has either repeated rows or repeated columns. Translating back to quantum optics, this lets us classically estimate the probability of any outcome of an AA-type experiment -- even an outcome involving multiple photons "bunched" in the same mode -- at least as well as that probability can be estimated by the experiment itself. It also yields a general upper bound on the probabilities of "bunched" outcomes, which resolves a conjecture of Gurvits and might be of independent physical interest. Second, we use
ε-biased sets to derandomize Gurvits's algorithm, in the special case where the matrix A is nonnegative. More interestingly, we generalize the notion of
ε-biased sets to the complex numbers, construct "complex
ε-biased sets", then use those sets to derandomize even our generalization of Gurvits's algorithm to the case (again for nonnegative A) where some rows or columns are identical. Whether Gurvits's algorithm can be derandomized for general A remains an outstanding problem.