Traditionally the theories of computation, and information have been studied independent of the physical theories governing the universe. But toward the end of twentieth century many researchers began to realize that computers that exploited the principles of quantum mechanics for representing and processing information could be more powerful than those which did not. One important consequence of this development has been the discovery that quantum computers can solve certain problems exponentially faster than a classical computer. However, quantum information is extremely fragile and reliable computation in the presence of noise is possible only when undergirded by fault tolerant information processing mechanisms. Thus a dominant theme of my research is to enable fault tolerant quantum computation bringing into bearing the theory of error correction to address this problem efficiently. Quantum computers raise a host of questions which are of fundamental import to various other disciplines. Hence another goal of my research is to translate the insights emerging from the study of quantum information processing for the classical world. Broadly, my research interests are in the fields of quantum computation and quantum information and their interplay with the fields of coding theory, algorithms, physics, and discrete mathematics. Specifically, my research centers around quantum error correction, quantum cryptography, study of mathematical structures in quantum computation, alternative models of computation and fault tolerance. Below I give a brief summary of my research.
Matroids are useful mathematical structures that find applications in many areas such as optimization, graph theory, error correcting codes and cryptography. However, matroids are yet to find comparable applications in quantum computation. Partly motivated by my research in quantum secret sharing (discussed below), I am currently investigating the applications of matroids in quantum information. In a recent work [P1] (with Raussendorf) I showed that matroids can be useful in the classification of certain classes of quantum states with respect to their equivalence. More precisely, we showed that a class of stabilizer states whose local Clifford and local unitary equivalence classes are distinct must arise from matroids that are neither graphic or cographic. Such states are useful for at least two reasons. Their structure could further our understanding of the phenomenon of entanglement, which is at the heart of all quantum computation. Secondly, they could themselves be resources for quantum computations which could provide speedup over classical computations. I intend to explore further the applications of matroids, especially to develop a comprehensive quantum matching theory. A step in this direction has already been taken by Gurvits, although the structure therein is somewhat more general that of matroids.
Quantum information can not only be used for computation but also for cryptographic purposes and it makes possible certain cryptographic tasks much more securely than with classical information alone. However, much of the emphasis in quantum cryptography has been placed on secure quantum key distribution, other cryptographic protocols such as quantum secret sharing (QSS) have not been investigated as much. In addition to protecting securing information, secret sharing also finds application in secure distributed computing. My research in quantum cryptography is aimed at understanding the interplay between secret sharing, codes and matroids as elaborated below.
Secret sharing and error correction are very closely related so much so that in the classical case one can always convert a secret sharing scheme into a error correcting code and vice versa. Such a complete association is not possible for QSS. Not every quantum code can be converted to a secret sharing scheme though we can regard every secret sharing scheme as a quantum code. Building upon Adam Smith's work on quantum secret sharing schemes for general access structures I show (with Klappenecker) how to derive a quantum secret sharing scheme from CSS codes, [J3]. These results also characterize the access structure of the scheme in terms of the minimal codewords of the underlying code.
Classically, secret sharing schemes induced by matroids are the most efficient secret schemes and the connections between matroids and secret sharing schemes have been extensively studied. Currently there is no well developed theory that relates quantum secret sharing schemes to matroids. My recent research (with Raussendorf) [P2] has taken the first steps toward a matroidal characterization of quantum secret sharing schemes. It also shows how to derive efficient quantum secret sharing schemes from self-dual representable matroids. When we can associate a matroid to a secret sharing scheme we say that it is matroid related. Seymour has shown that all matroid related secret sharing schemes can be characterized by an excluded matroid minor theorem. This begs the obvious questions if such structural results exist for quantum secret sharing schemes. My research aims at uncovering similar structures for the quantum secret sharing schemes. Matroidal characterization of quantum secret sharing schemes can not only help in the construction of efficient quantum secret sharing schemes but also provide with new techniques to study and analyze them.
My early research focused on understanding and clarifying many aspects of quantum stabilizer codes over a nonbinary alphabet. The motivation for considering nonbinary codes was that some of the best classical codes are over a large alphabet. Considering the close connections between classical codes and quantum codes, a similar behavior was expected. In this context my research also clarified these connections to classical codes identifying the largest class of classical codes that can be used for constructing quantum codes. My work provided many systematic constructions of quantum codes over a nonbinary alphabet and extended the framework of the nonbinary quantum codes, (initiated by Rains; Ashikhmin and Knill). It also clarified many ideas related to constructing new codes from existing codes. In particular the theory of puncture codes introduced by Rains was significantly extended.
Stabilizer codes are not the only means to protect quantum information. Much of the error correction in stabilizer codes is active. But in some sense active error correction is not very desirable, as we can potentially introduce errors in the process of error correction itself. Therefore many researchers have invested their efforts to investigating passive forms of error correction such as decoherence free subspaces, noiseless subsystems. A recent development due to Kribs et al., called operator quantum error correction unifies both paradigms of error correction. Following the lead of Poulin who proposed a stabilizer framework for understanding these codes, my later work deals with this generalization in a greater depth and making use of the framework of Clifford codes provides a natural understanding of these codes while at the same time making a useful connection with classical codes. In particular, it became clear through my work that operator quantum error correcting codes can be systematically constructed from existing classical codes by a very simple method. My work also showed that these codes do not require the restriction of self-orthogonality that is essential for stabilizer codes.
Much of quantum coding theory was developed within the umbrella of a noise model called the depolarizing channel. Though conceptually simpler, this is not the only form of noise model nor is it the most physical form of noise model. There are various other models that might more accurately reflect the physical mechanisms of noise. One such model is the asymmetric noise model under which different types of errors have different probabilities. I have recently been involved in development of a rigorous theory of quantum codes for asymmetric quantum channels and gave many systematic constructions of codes. These codes are in some measure better optimized to the channel than the usual stabilizer codes.
Stabilizer codes and their generalization the operator quantum error correcting codes fall within the class of quantum block codes. Classically convolutional codes offer an alternative to block codes because they have simple encoding schemes based on shift registers and very efficient decoding schemes. Quantum analogues of convolutional codes exist, within a stabilizer framework (developed Ollivier and Tillich), but the theory was not as transparent as that of quantum block codes. I was involved in the development of a direct limit framework for convolutional codes which provided a much more rigorous justification for many results in this area. In addition this led to new families of quantum convolutional codes, some of which were shown to be optimal.