Technical Report PHD-2007-10

Title: Classicality and Quantumness in Quantum Information Processing
Authors: Dan Kenigsberg
Supervisors: Tal Mor
Abstract: 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/. The most celebrated achievement of quantum computation is Shor's algorithm, which factors large integers in polynomial time. Other achievements are Simon's restricted collision-finding algorithm which is exponentially faster than its classical equivalent, and Grover's search algorithm which finds a specific element in an unordered database in time which is in the order of the square root of the size of that database.

A fundamental question looms over QIP (and quantum computation in particular): Where does its surprising advantage come from? What is the nonclassical property of quantum mechanics that leads to this computational superiority? A long thread of research in the field looks for the answer. Entanglement, which is a strong non-classical type of non-local correlations is often suggested as a key ingredient of quantum computation. In various occasions, separable quantum states (that are not entangled) have been considered mere classical. In my own 2001 M.Sc. thesis I suggested an evidence to strengthen this point of view.

In this research we provide a basis-independent definition for classicality of states, protocols and operations in quantum information processing. According to this definition, separable states /can/ be quantum. In fact, most of them are. We show a variety of nonentangled (separable) states that exhibit interesting quantum properties, and we explore the ``zoo'' of separable states; several interesting subclasses are defined based on their diagonalizing bases, and their non-classical behavior is investigated.

We present a few examples of separable (yet quantum) states, and show algorithms that are better than classical algorithms even when no entanglement is present. Furthermore, we show that quantum algorithms can be better than classical algorithms 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 is the amount of time required to obtain the solution, as a function of the input size. In oracle setting this usually means the number of queries needed to gain a predefined amount of information about the solution. 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 probability to obtain the correct answer is better for the quantum algorithm than for the optimal classical algorithm, and that the information gained by that single query is higher. For the Deutsch-Jozsa and Simon problems, this is true even when no entanglement is ever present throughout the quantum computation and even when the state of the quantum computer is arbitrarily close to being totally mixed.

We find an even clearer advantage of entanglement-free quantum computation over classical computation, in exact pure-state computation. For the Deutsch-Jozsa problem we find the maximal subproblem that can be solved without entanglement, and show that the Deutsch-Jozsa algorithm still has a non-negligible advantage over the best classical algorithm. We further prove that this subproblem contains all Boolean functions whose quantum phase-oracle is non-entangling.

Our research is not restricted to quantum algorithms. The question of how ``quantum'' a protocol should be in order to achieve a significant advantage over all classical protocols is of wide interest. We extend this discussion into another subfield of QIP: /quantum cryptography/. Secure key distribution among two remote parties is impossible when both are classical, unless some unproved (and arguably unrealistic) computation-complexity assumptions are made, such as the difficulty of factorizing large numbers. On the other hand, a secure key distribution /is/ possible when both parties are quantum. What is possible when only one party (Alice) is quantum, yet the other (Bob) has only classical capabilities? We present two protocols with this constraint, and prove their robustness against attacks: we prove that any attempt of an adversary to obtain information (and even a tiny amount of information) necessarily induces some errors that the legitimate users could notice.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2007
To the main CS technical reports page

Computer science department, Technion