| We study two novel paradigms in quantum error correction and quantum cryptography---approximate quantum error correction and noisy-storage cryptography---which explore alternate approaches for dealing with quantum noise. Approximate quantum error correction seeks to relax the constraint of perfect error correction and construct codes that might be better adapted to correct for specific noise models. Noisy-storage cryptography relies on the power of quantum noise to execute two-party cryptographic tasks securely.;Motivated by examples of approximately correcting codes, which make use of fewer physical resources than perfect codes and still obtain comparable levels of fidelity, we study the problem of finding and characterizing such codes in general. We construct for the first time a universal, near-optimal recovery map for approximate quantum error correction (AQEC), with optimality defined in terms of worst-case fidelity. Using the analytical form of this recovery, we also obtain easily verifiable conditions for AQEC. This in turn leads to a simple algorithm for identifying good approximate codes, without having to perform a difficult optimization over all recovery maps for every possible encoding.;Noisy-storage cryptography envisions a setting where two-party cryptographic protocols can be securely implemented based solely on the assumption that the quantum storage device possessed by either party is noisy and bounded. Here, we construct two-party protocols (using higher-dimensional states) that are secure even when a dishonest player can store all but a small fraction of the information transmitted during the protocol, in his noiseless quantum memory. We also show that when his memory is noisy, security can be extended to a larger class of noisy quantum memories. Our result demonstrates that the physical limits of the quantum noisy-storage model are indeed achievable, albeit asymptotically.;We also describe our investigations on obtaining strong entropic uncertainty relations using symmetric complementary bases. Uncertainty relations are an important and useful resource in analyzing the security of quantum cryptographic protocols, in addition to being of interest from a foundational standpoint. We present a novel construction of sets of symmetric, complementary bases in dimension d = 2n, which are cyclically permuted under the action of a unitary transformation. We also obtain new lower bounds for uncertainty relations in terms of the min-entropy, which are tight for specific instances of our construction. |
