Ph.D Thesis | |

Ph.D Student | Kenigsberg Dan |
---|---|

Subject | Classicality and Quantumness in Quantum Information Processing |

Department | Department of Computer Science |

Supervisor | ASSOCIATE PROF. Tal Mor |

Full Thesis text |

Quantum information processing (QIP) is a growing interdisciplinary field of information theory that tries to understand how information can be manipulated, communicated or extracted, while taking into account the quantum nature of the physical world. An important subfield of QIP is quantum computation, whose most celebrated achievement is Shor's factoring of large integers in polynomial time.

A fundamental question looms over QIP: Where does its surprising advantage come from? Entanglement, which is a strong non-classical type of correlation, is often suggested as a key ingredient of quantum computation. In various occasions, separable (non-entangled) quantum states have been considered mere classical.

We provide a basis-independent definition for classicality of states, protocols and operations in QIP. According to this definition, separable states can be quantum. We show a variety of separable states that exhibit interesting quantum properties and explore the "zoo" of separable states.

We present a few examples of separable (yet quantum) states, and show algorithms that are better-than-classical even when no entanglement is present. Furthermore, we show that quantum algorithms can be better-than-classical even when the state of the computer is almost totally mixed---which means that it contains an arbitrarily small amount of information.

The most usual measure of efficiency for algorithms in oracle setting is the number of queries needed to gain the solution as a function of the input size. Here, we fix the number of oracle calls and try to obtain as much Shannon information as possible about the correct answer. In this setting, we analyze three famous problems due to Deutsch-Jozsa, Simon and Grover. We show that, when a single oracle query is allowed, the information gained by the quantum algorithm is higher than by the optimal classical algorithm. For the Deutsch-Jozsa and Simon problems, this is true even without entanglement.

We extend the discussion of how "quantum" should a protocol be in order to become better-than-classical, into another subfield of QIP: quantum cryptography. Secure key distribution among two remote parties is impossible when both are classical, unless some unproved computation-complexity assumptions are made. On the other hand, a secure key distribution is possible when both parties are quantum. What is possible when only one party is quantum, yet the other has only classical capabilities? We present two protocols with this constraint, and prove that any attempt of an adversary to obtain information necessarily induces some errors that the legitimate users could notice.