Quantum computation and information has become a central research area in theoretical computer science. It studies how information is encoded in nature according to the laws of quantum mechanics and what this means for its computational power. On one hand, the ability of a quantum system to be in a superposition of states provides a way to encode an exponential amount of information in a quantum state. However, this information is accessible only indirectly via measurements. The goal of this thesis is precisely to investigate the fundamental question of how information is encoded and processed in quantum mechanical systems. (1) We investigate their power relative to classical encodings in the model of one-way communication complexity and show that they can be exponentially more efficient, answering a long standing open question in the area of quantum communication complexity. (2) We show how the theory developed for the study of quantum information can be employed in order to answer questions about classical coding theory and complexity. We resolve a main open question about the efficiency of Locally Decodable Codes by reducing the problem to one about quantum codes and solving the latter using tools from quantum information theory. This is the first example where quantum techniques are essential in resolving a purely classical question. (3) We investigate the power of quantum encodings in the area of cryptography. We study certain cryptographic primitives, such as Private Information Retrieval, Symmetrically-Private Information Retrieval and Coin Flipping.
Quantum computation and information has become a central research area in theoretical computer science. It studies how information is encoded in nature according to the laws of quantum mechanics and what this means for its computational power. On one hand, the ability of a quantum system to be in a superposition of states provides a way to encode an exponential amount of information in a quantum state. However, this information is accessible only indirectly via measurements. The goal of this thesis is precisely to investigate the fundamental question of how information is encoded and processed in quantum mechanical systems. (1) We investigate their power relative to classical encodings in the model of one-way communication complexity and show that they can be exponentially more efficient, answering a long standing open question in the area of quantum communication complexity. (2) We show how the theory developed for the study of quantum information can be employed in order to answer questions about classical coding theory and complexity. We resolve a main open question about the efficiency of Locally Decodable Codes by reducing the problem to one about quantum codes and solving the latter using tools from quantum information theory. This is the first example where quantum techniques are essential in resolving a purely classical question. (3) We investigate the power of quantum encodings in the area of cryptography. We study certain cryptographic primitives, such as Private Information Retrieval, Symmetrically-Private Information Retrieval and Coin Flipping.
One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet there are ways of conveying information with exponentially fewer qubits than possible classically. Moreover, these methods have a very simple structure---they involve little interaction between the communicating parties. We look more closely at the ways in which information encoded in quantum states may be manipulated, and consider the question as to whether every classical protocol may be transformed to a ``simpler'' quantum protocol of similar efficiency. By a simpler protocol, we mean a protocol that uses fewer message exchanges. We show that for any constant k, there is a problem such that its k+1 message classical communication complexity is exponentially smaller than its k message quantum communication complexity, thus answering the above question in the negative. Our result builds on two primitives, local transitions in bi-partite states (based on previous work) and average encoding which may be of significance in other applications as well.
Quantum information processing (QIP) studies the representation, manipulation, and transmission of information using quantum systems. By leveraging counterintuitive quantum phenomena such as superposition and entanglement, QIP enables new paradigms for computation, communication, and learning that can surpass classical limits in certain regimes. Foundational tasks in QIP include quantum data compression, quantum communication, and quantum learning and optimization, which together form the basis for scalable quantum technologies. This thesis develops new frameworks and algorithms at the intersection of quantum information theory, quantum learning, and quantum-inspired modeling. The thesis is organized into three parts. The first part studies quantum compression problems; the second addresses quantum communication; and the third develops quantum learning and optimization frameworks with applications to complex systems. In the first part, a new formulation for lossy quantum-classical source coding, termed rate-channel theory, is introduced, replacing the conventional distortion-based formulation with a posterior-channel-based framework under a block-error criterion. The framework is further generalized to incorporate quantum side information at the decoder. A connection between rate-channel theory and classical rate-distortion theory is also established, showing that optimal rate-distortion performance can be recovered under suitable conditions. These results provide a unified and flexible framework for data compression, which is essential for scalable quantum computing infrastructure, enabling efficient storage of quantum data, such as outputs from quantum sensors (e.g., MRI) and information encoded in photonic systems for satellite and optical communication. In the second part, the problem of computing functions of distributed sources over classical-quantum multiple access channels is studied. A new coding framework is developed that combines algebraic structured codes with unstructured random coding techniques, enabling efficient communication of functions without reconstructing individual sources. The resulting achievable conditions, expressed in terms of single-letter quantum information quantities, strictly enlarge the class of sources for which reliable computation is possible. These results contribute to the theoretical foundations of quantum network communication and are directly relevant to deep-space satellite-based quantum communication, distributed quantum computing, and the design of scalable quantum network infrastructures. In the final part, new approaches to quantum learning and optimization are developed. A geometry-aware quantum optimization framework is proposed based on a novel quantum information metric and an unbiased estimator constructed from single-shot measurements. This leads to an optimization method with constant sample complexity per iteration and provable exponential convergence under mild conditions, while avoiding saddle points and local minima. Such advances are particularly relevant for challenging optimization tasks in quantum sensing and quantum computational modeling of many-body systems. Building on this optimization framework, a Hamiltonian learning approach is introduced to infer interaction structures from time-resolved measurement data, with finite-sample guarantees and polynomial scaling with system size. This framework is further extended to develop a quantum-inspired generative model for gene regulatory network inference, where interactions are encoded as a parameterized Hamiltonian evolving over pseudotime. The proposed methods demonstrate strong performance on synthetic benchmarks and reveal biologically meaningful structures in real-world data, with applications to multi-omics integration, cancer genomics, and systems biology. Overall, this thesis advances the theoretical and algorithmic foundations of quantum information processing, with contributions spanning compression, communication, and learning. These developments support the design of resource-efficient and scalable quantum technologies, enabling applications in quantum sensing, quantum networks, distributed quantum computation, and the modeling of complex physical and biological systems.
This thesis is a study of how information theory can be used to analyse and interpret quantum mechanical systems, specifically, systems that are being used for information processing and communication tasks. Quantum information science is a relatively new field, and it has only been recently that we have started to look at using quantum mechanical systems to accomplish information processing tasks that are not possible using classical systems. As this method of information processing is a relatively new paradigm, there are many possibilities for new algorithms and discoveries in this area of computing. The application of information theory towards the analysis and description of quantum mechanical systems yields new interesting results - it can even be argued that information theory provides a natural and intuitive way to intepret quantum mechanics, as correlations and measurement outcomes in quantum processes can be described using information theory. Chapter 1 is an introduction to the strange new world of quantum mechanics and takes a brief look at one of the applications of quantum information science in quantum cryptography. A mathematical overview of the postulates and framework that quantum mechanics is built on is presented in Chapter 2. Chapter 3 is a brief study of classical information theory and some of the fundamental concepts and ideas that form the crux of the subject. In Chapter 4, we present the main results of the thesis by taking a look at an optimal measurement scheme that improves on previous schemes by allowing us to extract the maximal amount of information from states in a quantum channel of specific geometry. The findings have an impact on various other areas of the field, including security analysis of quantum cryptographic protocols and building better quantum cloning machines.
This paper investigates the core methods of information encoding and decoding within quantum networks, aiming to enhance both the efficiency and security of quantum information transmission. We explore various encoding schemes, including amplitude encoding, phase encoding, and polarization encoding, alongside their corresponding decoding strategies. The core mechanism relies on manipulating quantum states to represent and transmit information securely. Our research focuses on optimizing these processes to mitigate the effects of noise and loss, critical challenges in long-distance quantum communication. We delve into error correction techniques specifically tailored for quantum systems, such as quantum error correction codes (QECCs) and their application in decoding. Furthermore, we examine the role of quantum key distribution (QKD) protocols as a fundamental decoding process, highlighting the security aspects derived from the laws of quantum mechanics. The ultimate goal is to provide a comprehensive overview of the current state-of-the-art in quantum network information encoding and decoding, paving the way for future advancements in quantum communication technologies.
What are the information processing capabilities of physical systems?As recently as the first half of the 20 th century this question did not even have a definite meaning.What is information, and how would one process it?It took the development of theories of computing (in the 1930s) and information (late in the 1940s) for us to formulate mathematically what it means to compute or communicate.Yet these theories were abstract, based on axiomatic mathematics: what did physical systems have to do with these axioms?Rolf Landauer had the essential insight -"Information is physical" -that information is always encoded in the state of a physical system, whose dynamics on a microscopic level are well-described by quantum physics.This means that we cannot discuss information without discussing how it is represented, and how nature dictates it should behave.Wigner considered the situation from another perspective when he wrote about "the unreasonable effectiveness of mathematics in the natural sciences".Why are the computational techniques of mathematics so astonishingly useful in describing the physical world [1]?One might begin to suspect foul play in the universe's operating principles.Interesting insights into the physics of information accumulated through the 1970s and 1980s -most sensationally in the proposal for a "quantum computer".If we were to mark a particular year in which an explosion of interest took place in information physics, that year would have to be 1994, when Shor showed that a problem of practical interest (factorisation of integers) could be solved easily on a quantum computer.But the applications of information in physics -and vice versa -have been far more widespread than this popular discovery.These applications range from improved experimental technology, more sophisticated measurement techniques, methods for characterising the quantum/classical boundary, tools for quantum chaos, and deeper insight into quantum theory and nature.In this thesis I present a short review of ideas in quantum information theory.The first chapter contains introductory material, sketching the central ideas of probability and information theory.Quantum mechanics is presented at the level of advanced undergraduate knowledge, together with some useful tools for quantum mechanics of open systems.In the second chapter I outline how classical information is represented in quantum systems and what this means for agents trying to extract information from these systems.The final chapter presents a new resource: quantum information.This resource has some bewildering applications which have been discovered in the last ten years, and continually presents us with unexpected insights into quantum theory and the universe.ii This thesis is dedicated to my mother.iii This thesis was begun as an intrepid adventure.It caught
Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles such as the superposition principle, entanglement, and interference. Until recently the common notion of computing was based on classical mechanics and did not take into account all the possibilities that physically realizable computing devices offer in principle. The field gained momentum after Shor developed an efficient algorithm for factoring numbers, demonstrating the potential computing powers that quantum computing devices can unleash. In this review the information counterpart of computing is studied. It was realized early on by Holevo that quantum bits, the quantum mechanical counterpart of classical bits, cannot be used for efficient transformation of information in the sense that arbitrary k-bit messages cannot be compressed into messages of $k\ensuremath{-}1$ qubits. The abstract form of the distributed computing setting is called communication complexity. It studies the amount of information, in terms of bits or in our case qubits, that two spatially separated computing devices need to exchange in order to perform some computational task. Surprisingly, quantum mechanics can be used to obtain dramatic advantages for such tasks. The area of quantum communication complexity is reviewed and it is shown how it connects the foundational physics questions regarding nonlocality with those of communication complexity studied in theoretical computer science. The first examples exhibiting the advantage of the use of qubits in distributed information-processing tasks were based on nonlocality tests. However, by now the field has produced strong and interesting quantum protocols and algorithms of its own that demonstrate that entanglement, although it cannot be used to replace communication, can be used to reduce the communication exponentially. In turn, these new advances yield a new outlook on the foundations of physics and could even yield new proposals for experiments that test the foundations of physics.