|
Seminar Announcement Date: Friday, 22 November 2024 Time: 4 to 5 PM Venue: LH202 A derandomization approach in quantum information processing with applications in benchmarking a quantum gate and finding channels with superadditive classical capacity; and a One-shot cost region for Multiple Access Channel Simulation. Aditya Nema RWTH Aachen University, Germany. 22-11-24 Abstract
In this talk, we will first see a derandomization technique in quantum computation and information processing. Quantum logic gates (and hence circuits) are generally unitary operators and in order to prove existential results via a probabilistic method one needs to sample these unitary operators randomly. The distribution of a unitary operator chosen uniformly at random from the unitary group is described via the Haar measure and we call these as Haar random unitaries. It is proven that the sampling and implementation of Haar random unitaries are exponentially hard. Hence, we consider one finite (pseudorandom) ensemble of unitaries which mimics Haar random unitaries approximately, upto first -moments (over a polynomial in entries of the unitary). This pseudorandom ensemble of unitaries is called an approximate unitary design. Brandao et al. (2012) and Sen (2019) have shown that approximate unitary -designs can be constructed efficiently if the value of the parameter . We first describe a known method of Low et al. (2009) of using these designs analogous to -wise independent random variables and find large deviation bounds for polynomials in entries of such unitaries. This leads to replacing Haar random unitaries via designs and we shall refer to this process as derandomization. We then come to the first task of constructing efficient algorithms for benchmarking a quantum logic gate using these designs. Our algorithms use less random bits and do a tighter error analysis than the state of art. This is one of the fundamental steps in experimentally implementing a quantum computer (given the reliability of the building blocks for quantum gates). We then consider the problem of finding quantum channels that have single letter characterization of the classical capacity also called the Holevo capacity. Holevo capacity is the maximum rate at which classical information can be transmitted over a quantum channel. This is the first generalization of classical information theory in a quantum setting. Hastings(2008) in a major breakthrough, proved for the first time that there exists quantum channels exhibiting superadditive Holevo capacity, which was conjectured otherwise (Holevo, 2000) and in fact the conjecture was shown to be true for a wide variety of channels. This superadditivity of Holevo capacity implies that the quantum channels may not always have a single letter capacity formula, making it extremely difficult to compute and construct "optimal" error correction codes. Hastings used channels that are represented by choosing Haar random unitaries (). Constructing these channels (even approximately) requires exponentially many qubits (, ). Hence, the hunt for efficient channels having superadditive Holevo capacity has been a long-standing open problem. We take a step in this direction by aiming to derandomize Hastings counter example. In particular, we consider channels sampled uniformly from approximate unitary -designs and show that these channels have superadditive Holevo capacity with exponentially high probability. Although the value of the design parameter in our counterexample (for additivity of Holevo capacity) is , we still save a lot in terms of random bits () for implementation leading to a partial derandomization. We use tools from geometric functional analysis to do a novel stratified analysis of the unit -sphere () and prove a measure concentration theorem for the random subspaces coming from . This leads to proving a discretized version of the so-called Dvoretzky's theorem (not to be discussed in the talk). An advantage of our main result is that it can be directly used to unify the previous analysis on this problem. We will finally discuss the problem of _universally_ simulating a classical Multiple Access Channel in the one-shot setting with independent inputs and infinite shared randomness. We show that we have an almost tight one-shot universal rate region for MAC, which we prove is tight asymptotically. The achievability is based on an elegant rejection sampling technique and converse is shown using a novel information-spectrum inspired technique. One-shot rate region is characterized in terms of the smoothed max-mutual information. Brief bio: Aditya Nema, RWTH Aachen University, Germany About : I did my Master's and Ph.D. from STCS, TIFR, Mumbai in Quantum Information Theory on derandomizing Haar random unitaries via approximate unitary -designs to search for computationally efficient protocols. This involved, derandomizing the seminal result of Hastings that there exists quantum channels with superadditive classical capacity, prove a measure concentration for the decoupling theorem and construct efficient benchmarking protocols for a quantum logic gate. After PhD, I was a Specially Appointed Assistant Prof. in Nagoya University, Japan continuing research in quantum information (Shannon) theory and resource theory. At present I am a postdoc in the Institute of Quantum Information, Department of Physics at RWTH Aachen University. My research interests are in classical and quantum information theory, quantum computing and applied probability.
|
