Quantum Computation: Foundations, Security, Cryptography and Group Theory
Lead Research Organisation:
University of York
Department Name: Computer Science
Abstract
Quantum computation is based on computers which operate on the level of quantum mechanics rather than classical electronics. The advantage of this is that in quantum mechanics entities can be simultaneously in many different positions at once: and this allows states of a quantum computer to behave in some ways like a stack of parallel states. This parallel stack does not unfortunately come without strings and, because of the physics of quantum mechanics, it is very difficult to find out what is in any such stack at a particular time: so reading the output of a quantum computer is not easy. Some powerful quantum algorithms have been developed: for example by Shor to factor integers much faster than conventional algorithms can. However the number of such algorithms that we know is not growing very rapidly. One reason for this is that we do not have a systematic understanding of how to build up quantum computing algorithms and indeed do not have a comprehensive library of algorithms for very basic functions and procedures for building from them. The main aims of this project are to construct such a systematic foundation for quantum computation and to establish procedures for basic processes.We shall test our success in these objectives by attempting to construct algorithms for problems which arise in group theory. This area of mathematics provides an endless array of algorithmic problems at all levels of difficulty, so is a good test bed for a potential computation system.We shall also consider how to extend the analysis of cryptographic systems from classical schemes to quantum schemes. In particular this is expected to allow us to build an automated voting process which cannot be tampered with or broken into, by the people who run it.
Organisations
People |
ORCID iD |
| Samuel Braunstein (Principal Investigator) |
Publications
Braunstein S
(2011)
Zero-error subspaces of quantum channels
Braunstein SL
(2011)
Black hole evaporation rates without spacetime.
in Physical review letters
Patra M
(2011)
Quantum Fourier transform, Heisenberg groups and quasi-probability distributions
in New Journal of Physics
Pirandola S
(2009)
Confidential Direct Communications: A Quantum Approach Using Continuous Variables
in IEEE Journal of Selected Topics in Quantum Electronics
Pirandola S
(2009)
Direct and reverse secret-key capacities of a quantum channel.
in Physical review letters
Pirandola S
(2009)
Theory of Quantum Computation, Communication, and Cryptography
| Description | We define the direct and reverse secret-key capacities of a memoryless quantum channel as the optimal rates that entanglement-based quantum-key-distribution protocols can reach by using a single forward classical communication (direct reconciliation) or a single feedback classical communication (reverse reconciliation). In particular, the reverse secret-key capacity can be positive for antidegradable channels, where no forward strategy is known to be secure. This property is explicitly shown in the continuous variable framework by considering arbitrary one-mode Gaussian channels. We consider the problem of privacy in direct communications, showing how quantum mechanics can be useful to guarantee a certain level of confidentiality. In particular, we review a continuous variable approach recently proposed by us [EPL 84, 20013 (2008)]. Here, we analyze the degree of privacy of this technique against a broader class of attacks, which includes non-Gaussian eavesdropping. We consider the notion of canonical attacks, which are the cryptographic analog of the canonical forms of a one-mode Gaussian channel. Using this notion, we explore the connections between the degradability properties of the channel and its security for quantum key distribution. Finally, we also show some relations between canonical attacks and optimal Gaussian cloners. We propose an algebraic model for classical information theory. We first give an algebraic model of probability theory. Information theoretic constructs are based on this model. In addition to theoretical insights provided by our model we obtain new computational and analytical tools. Several important theorems of classical probability and information theory are presented in the algebraic framework. We explore the inherent connection between Heisenberg groups, quantum Fourier transform (QFT) and (quasi probability) distribution functions. Distribution functions for continuous and finite quantum systems are examined from three perspectives and all of them lead to Weyl-Gabor Heisenberg groups. The QFT appears as the intertwining operator of two equivalent representations arising out of an automorphism of the group. Distribution functions correspond to certain distinguished sets in the group algebra. The marginal properties of a particular class of distribution functions (Wigner distributions) arise from a class of automorphisms of the group algebra of the Heisenberg group. We then study the reconstruction of the Wigner function from the marginal distributions via inverse Radon transform giving explicit formulae. We consider some applications of our approach to quantum information processing and quantum process tomography. We take first tentative steps in achieving Verlinde's vision of a spacetime-free version of gravity by deriving the evaporation rate from black hole event horizons (i.e., the black hole radiation spectrum) in a spacetime-free manner. Our result relies on a Hilbert space description of black hole evaporation, symmetries therein which follow from the inherent high dimensionality of black holes, global conservation of the no hair quantities and the existence of Penrose processes. Our analysis is not wedded to standard General Relativity and so should apply to extended gravity theories where we find that black hole area must be replaced by some other property in any generalized area theorem. |
| Exploitation Route | Our understandings about gravity have led to a better understanding of black holes and led to a first description of energetic curtains (latter independently rediscovered and called black hole firewalls). This latter insight has had an enormous impact on the field and on the public. |
| Sectors | Other |
| Description | We established a coherent and natural framework for low level quantum processing, analogous to the framework provided by automata for classical computation. We then applied these results to develop algorithms in group theory, cryptography and secure distributed computation. We studied a range of models for processes at a low level of the Chomsky Hierarchy (which have not been so intensively studied to date) to try and find natural frameworks for their implementation. We developed suitably general definitions of automata in both the classical and quantum setting, in order to provide both algebraic models of state machines and semantics of combinatory algebras. The aim in this case was to use the algebraic models to form a general description of recognition, in order to describe classes of formal languages: such as analogues of regular and perhaps context-free languages. We applied the results of the first phase of the project, described above, to algorithmic problems in group theory. In particular in order to develop quantum algorithms for some basic decision problems in particular classes of groups, e.g., for non-Abelian infinite groups which have not been much studied in the context of quantum computation. |
| First Year Of Impact | 2009 |
| Sector | Other |
| Impact Types | Cultural |