The framework of distributed computing, consisting of several spatially separated input-output servers, has immense importance in distant data manipulation. One of the most challenging parts of this setting is to optimize the use of information transmission lines among distant servers. In this work, we have modeled such a physically motivated distributed computing setup for which quantum communication outperforms its classical counterpart, in terms of a limited usage of noiseless transmission lines. Moreover, a broader class of communication entities, that allow state-effect description more exotic than quantum and are described within the framework of generalized probabilistic theory, also fail to meet the strength of quantum theory. The computational strength of quantum communication has further been justified in terms of a stronger version of this task, namely the delayed-choice distributed computation. The proposed task thus provides a new approach to operationally single out quantum theory in the theory-space and hence promises a novel perspective towards the axiomatic derivation of Hilbert space quantum mechanics.
The framework of distributed computing, consisting of several spatially separated input-output servers, has immense importance in distant data manipulation. One of the most challenging parts of this setting is to optimize the use of information transmission lines among distant servers. In this work, we have modeled such a physically motivated distributed computing setup for which quantum communication outperforms its classical counterpart, in terms of a limited usage of noiseless transmission lines. Moreover, a broader class of communication entities, that allow state-effect description more exotic than quantum and are described within the framework of generalized probabilistic theory, also fail to meet the strength of quantum theory. The computational strength of quantum communication has further been justified in terms of a stronger version of this task, namely the delayed-choice distributed computation. The proposed task thus provides a new approach to operationally single out quantum theory in the theory-space and hence promises a novel perspective towards the axiomatic derivation of Hilbert space quantum mechanics.
Computation refers to an algorithmic process of producing outputs from a given set of inputs. We consider a particular model of computation where the computing device is comprised of several components/ports placed at different spacetime locations -- the inputs are distributed among different ports, whereas the output is to be assessed by some other port. Importantly, communications among the different ports are limited as the physical systems allowed to be transmitted among the different ports are constrained with information theoretic restrictions. Interestingly, this limited communication distributed computing prototype provides an efficient modus operandi to compare the computational strength of different mathematical models used to describe those physical systems. We come up with computing tasks where quantum theory outperforms its classical counterpart. More surprisingly, a broader class of operational theories with state or/and effect space structures more exotic than quantum theory turns out to be suboptimal in performing some distributed computing tasks. We characterize the computations that can be perfectly accomplished in quantum theory but not in other theories. The proposed computing model thus provides a new approach to single out quantum theory in the theory space and promises a novel perspective towards the axiomatic derivation of Hilbert space quantum mechanics.
Quantum mechanics has been a paradigm shift and a revolutionary framework in our understanding of the physical world. The theory has been able to describe a wide variety of phenomena and has been experimentally verified with great precision. Despite that, to this day, the seemingly ad hoc formulation of quantum theory and several of its features still elude an intuitive understanding. At the same time, the applications of quantum mechanics in information theory have emerged as a promising avenue. Namely, its potential advantages in computation, in the so-called nascent field of quantum computation and in communication and information processing tasks such as quantum teleportation and super-dense coding. In all these endeavours, a significant effort has been made in understanding the maximum extent to which quantum mechanics can provide an advantage. This thesis explores an intersection of these two research lines, i.e. to have a physical explanation of some of the features of quantum mechanics and at the same time, study the outer limits of quantum mechanics. The combining insight rests on a newer foundational idea: that information itself is physical rather than an abstract entity and thus, is subject to physical laws. In this thesis, we explore the principle of information causality, which states that in any communication scenario, the amount of information carried is bounded by the degrees of freedom of the carrier. Information causality was initially proposed as a physical principle aimed at deriving the predictions of quantum mechanics on the type of correlations observed in a Bell scenario, which is a communication scenario involving multiple parties with access to a shared randomness resource. This principle has been proposed to recover some of the well-known features of quantum mechanics, specifically Tsirelson’s bound of the Clauser-Horne-Shimony-Holt inequality. Earlier results found limited generalisations due to the difficulty of deducing implications of the information causality principle. In this thesis, we greatly expand the scope of applicability of the principle. We develop a general-purpose algorithm to derive constraints on the set of quantum correlations. We extend the principle to be applicable to a wider variety of Bell scenarios, derive new families of quantum Bell inequalities and prove new bounds on the success probabilities of Entanglement Assisted Random Access Codes. We introduce an extension of the principle which applies to any distributed computing scenario. Using this extension, we improve on several previously known results in the field, and in certain cases, we even recover part of the quantum set as well. This extension provides rich insights into the communication complexity of distributed functions, using which we prove theory-independent randomised communication complexity bounds for several well-known functions and provide another general-purpose algorithm to bound the randomised quantum communication complexity of any function. As a consequence of the extension, we also establish that the extension supersedes the principle of non-trivial communication complexity.
Distributed quantum computation is a task in which many distant parties perform a large quantum computation in collaboration with each other, by using classical communication, quantum communication or shared entanglement as resources.In this thesis, we consider one of the simplest nontrivial task of distributed quantum computation, that is, implementation of bipartite unitary by LOCC (local operations and classical communication) assisted by shared entanglement.Here, two input states are distributed over two distant parties.Contrary to previous researches, we consider an asymptotic scenario in which the two parties perform the same bipartite unitary on infinitely many independent input pairs.We analyze the minimum amount of resources required for the task by exploiting concepts and techniques developed in the field of quantum Shannon theory, which has originally been developed to analyze quantum communication.As a tool for analyzing distributed quantum computation, we first introduce a task that we call Markovianization.Markovianization is a task in which a tripartite pure state is transformed to a state called quantum Markov chain, by a randomizing operation on one of the three subsystems.We derive the minimum cost of randomness required for Markovianization (Markovianizing cost) by exploiting a novel decomposition of a Hilbert space introduced in the context of quantum cryptography.We then apply the obtained result to distributed quantum computation.We mainly consider implementation of bipartite unitaries by entanglement-assisted LOCC protocols consisting of three steps, called one-round protocols.This is the first nontrivial case because it is not possible to implement bipartite unitaries by protocols consisting of only one or two steps.Our main result is that we derive the minimum costs of entanglement and classical communication.We show that the minimum costs are given by the Markovianizing cost of a tripartite state associated with the unitary.The result indicates that information about input states of computation is divided into three components: one of which only information of amplitude in a basis is required for computation (information of phase is not), another of which both amplitude and phase information are required, and the other of which no information is involved in computation.Our construction of a protocol that requires the smallest amount of resources is based on this decomposition.We also propose a method to compute the Markovianizing cost of a state associated with the unitary.We also consider two-round protocols, that is, protocols consisting of concatenation of two one-round protocols, for two-qubit controlled unitaries.We show that, for a particular class of two-qubit controlled unitaries, the minimum entanglement cost in two-round protocols is strictly smaller than that in one-round protocols.This result is the first reported case that indicates a property of a trade-off relation between entanglement requirement and the number of turns in entanglement-assisted LOCC tasks.The research in this thesis opens a possibility to build a new bridge between quantum computation theory and quantum communication theory, which are the two largest subfield of quantum information theory, by analyzing a problem in the former using concepts and techniques developed in the latter.
Full formal descriptions of algorithms making use of quantum principles must take into account both quantum and classical computing components and assemble them so that they communicate and cooperate.Moreover, to model concurrent and distributed quantum computations, as well as quantum communication protocols, quantum to quantum communications which move qubits physically from one place to another must also be taken into account. Inspired by classical process algebras, which provide a framework for modeling cooperating computations, a process algebraic notation is defined, which provides a homogeneous style to formal descriptions of concurrent and distributed computations comprising both quantum and classical parts.Based upon an operational semantics which makes sure that quantum objects, operations and communications operate according to the postulates of quantum mechanics, a probabilistic branching bisimulation is defined among processes considered as having the same behavior.
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.
This paper explores a novel approach to distributed computing leveraging the principles of quantum entanglement. The core claim is that direct information transfer, facilitated by entanglement, can circumvent the limitations of classical communication bottlenecks, ultimately enhancing computational efficiency and security. This research proposes encoding data into entangled states and utilizing their non-local properties to perform parallel computations. We detail a framework where manipulation of specific components within an entangled state impacts the entire system, enabling distributed computation. The potential for significant performance gains and improved security, compared to traditional distributed computing paradigms reliant on classical communication, is thoroughly discussed. The theoretical framework presented here offers a pathway for future research and development in quantum distributed computing systems.