We discuss the Bennett-Brassard 1984 (BB84) quantum key distribution protocol in the light of quantum algorithmic information. While Shannon's information theory needs a probability to define a notion of information, algorithmic information theory does not need it and can assign a notion of information to an individual object. The program length necessary to describe an object, Kolmogorov complexity, plays the most fundamental role in the theory. In the context of algorithmic information theory, we formulate a security criterion for the quantum key distribution by using the quantum Kolmogorov complexity that was recently defined by Vit\'anyi. We show that a simple BB84 protocol indeed distributes a binary sequence between Alice and Bob that looks almost random for Eve with a probability exponentially close to 1.
We discuss the Bennett-Brassard 1984 (BB84) quantum key distribution protocol in the light of quantum algorithmic information. While Shannon's information theory needs a probability to define a notion of information, algorithmic information theory does not need it and can assign a notion of information to an individual object. The program length necessary to describe an object, Kolmogorov complexity, plays the most fundamental role in the theory. In the context of algorithmic information theory, we formulate a security criterion for the quantum key distribution by using the quantum Kolmogorov complexity that was recently defined by Vit'anyi. We show that a simple BB84 protocol indeed distributes a binary sequence between Alice and Bob that looks almost random for Eve with a probability exponentially close to 1.
Quantum cryptography uses quantum mechanics to guarantee secure communication. BB84 is a widely used quantum key distribution that provides a way for two parties, a sender, Alice, and a receiver, Bob, to share an unconditionally secure key in the presence of an eavesdropper, Eve. Three different criteria can be assumed to study the BB84 protocol. They are the efficiency of the protocol, the probability that Eve remains undetected, and the amount of knowledge Eve has about Alice's bit sequence. In a previous approach, we only considered the probability that Eve remains undetected. We viewed this protocol as a three player static game in which Alice and Bob were two cooperative players and Eve was a competitive one. In our game model, Alice's and Bob's objective was to maximize the probability of detecting Eve, while Eve's objective was to minimize this probability. In this paper, our previous effort is extended and we also consider the other two criteria, i.e. the efficiency of the protocol and the amount of knowledge Eve has about Alice's bit sequence. Using these models, we show how game theory can be used to find the strategies for Alice, Bob and Eve.
In analogy of classical Kolmogorov complexity we develop a theory of the algorithmic information in bits contained in any one of continuously many pure quantum states: quantum Kolmogorov complexity. Classical Kolmogorov complexity coincides with the new quantum Kolmogorov complexity restricted to the classical domain. Quantum Kolmogorov complexity is upper bounded and can be effectively approximated from above. With high probability a quantum object is incompressible. There are two alternative approaches possible: to define the complexity as the length of the shortest qubit program that effectively describes the object, and to use classical descriptions with computable real parameters.
We extend algorithmic information theory to quantum mechanics, taking a universal semicomputable density matrix (`universal probability') as a starting point, and define complexity (an operator) as its negative logarithm. A number of properties of Kolmogorov complexity extend naturally to the new domain. Approximately, a quantum state is simple if it is within a small distance from a low-dimensional subspace of low Kolmogorov complexity. The von Neumann entropy of a computable density matrix is within an additive constant from the average complexity. Some of the theory of randomness translates to the new domain. We explore the relations of the new quantity to the quantum Kolmogorov complexity defined by Vitányi (we show that the latter is sometimes as large as 2 n − 2 log n ) and the qubit complexity defined by Berthiaume, Dam and Laplante. The `cloning' properties of our complexity measure are similar to those of qubit complexity.
The publication of the BB84 protocol by Bennett and Brassard in 1984 [10] marks the beginning of quantum key distribution. Since then, many other protocols have been invented. Yet, BB84 keeps a privileged place in the list of existing protocols: it is the one most analyzed and most often implemented, including those used in commercial products, e.g., [91, 113]. In this chapter, I define the BB84 protocol, although I already described it informally in Section 1.1. The physical implementation is then investigated. Finally, I analyze the eavesdropping strategies against BB84 and deduce the secret key rate. Description Alice chooses binary key elements randomly and independently, denoted by the random variable X ∈ χ = {0, 1}. In this protocol, there are two encoding rules, numbered by i ∈ {1, 2}. Alice randomly and independently chooses which encoding rule she uses for each key element. In case 1, Alice prepares a qubit from the basis {|0〉, |1〉} as In case 2, Alice prepares a qubit from the basis {|+〉, |−〉} as On his side, Bob measures either Z or X , yielding the result Y Z or Y X , choosing at random which observable he measures. After sending a predefined number of qubits, Alice reveals to Bob the encoding rule for each of them. They proceed with sifting, that is, they discard the key elements for which Alice used case 1 (or case 2) and Bob measured Z (or X ). For the remaining (sifted) key elements, we denote Bob's sifted measurements by Y .
Quantum key distribution uses quantum mechanics to guarantee secure communication. BB84 is a widely used quantum key distribution that provides a way for two parties, a sender, Alice, and a receiver, Bob, to share an unconditionally secure key in the presence of an eavesdropper, Eve. In a new approach, we view this protocol as a three player static game in which Alice and Bob are two cooperative players and Eve is a competitive one. In our game model Alice’s and Bob’s objective is to maximize the probability of detecting Eve, while Eve’s objective is to minimize this probability. Using this model we show how game theory can be used to find the strategies for Alice, Bob and Eve.
In this paper we give a definition for quantum Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a string is the length of the shortest program that can produce this string as its output. It is a measure of the amount of innate randomness (or information) contained in the string. We define the quantum Kolmogorov complexity of a qubit string as the length of the shortest quantum input to a universal quantum Turing machine that produces the initial qubit string with high fidelity. The definition of P. Vitanyi (2000) measures the amount of classical information, whereas we consider the amount of quantum information in a qubit string. We argue that our definition is natural and is an accurate representation of the amount of quantum information contained in a quantum state.