Search for: All records

As techniques for fault-tolerant quantum computation keep improving, it is natural to ask: what is the fundamental lower bound on space overhead? In this paper, we obtain a lower bound on the space overhead required for ϵ -accurate implementation of a large class of operations that includes unitary operators. For the practically relevant case of sub-exponential depth and sub-linear gate size, our bound on space overhead is tighter than the known lower bounds. We obtain this bound by connecting fault-tolerant computation with a set of finite blocklength quantum communication problems whose accuracy requirements satisfy a joint constraint. The lower bound on space overhead obtained here leads to a strictly smaller upper bound on the noise threshold for noise that are not degradable. Our bound directly extends to the case where noise at the outputs of a gate are non-i.i.d. but noise across gates are i.i.d. 

Both the search for extraterrestrial intelligence (SETI) and messaging extraterrestrial intelligence (METI) struggle with a strong indeterminacy in what data to look for and when to do so. This has led to attempts at finding both fundamental mathematical limits for SETI as well as benchmarks regarding specific signals. Due to the natural correspondence, previous information-theoretic work has been formulated in terms of communication between extraterrestrial and human civilizations. In this work, we instead formalize SETI as a detection problem, specifically (quantum) one-shot asymmetric hypothesis testing. This framework holds for all detection scenarios-in particular, it is relevant for detection of any technosignature, including quantum mechanical signals. To the best of our knowledge, this is the first work to consider the applicability of SETI for quantum signals. Using this formalism, we are able to unify the analysis of fundamental limits and benchmarking specific signals. To show a distinction between METI and SETI, we show that significantly weaker signals may be useful in detection in comparison to communication. Furthermore, the framework is computationally efficient, so it can be implemented by practicing astrobiologists.