Open Access Library Journal
Vol.02 No.08(2015), Article ID:68546,6 pages
10.4236/oalib.1101798

The Deutsch-Jozsa Algorithm Can Be Used for Quantum Key Distribution

Koji Nagata1, Tadao Nakamura2

1Department of Physics, Korea Advanced Institute of Science and Technology, Daejeon, Korea

2Department of Information and Computer Science, Keio University, Yokohama, Japan

Email: ko_mi_na@yahoo.co.jp, nakamura@pipelining.jp

Copyright © 2015 by authors and OALib.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

Received 20 July 2015; accepted 11 August 2015; published 14 August 2015

ABSTRACT

We review the new type of Deutsch-Jozsa algorithm proposed in [K. Nagata and T. Nakamura, Int. J. Theor. Phys. 49, 162 (2010)]. We suggest that the Deutsch-Jozsa algorithm can be used for quantum key distribution. Alice sends input N + 1 partite uncorrelated state to a black box. Bob measures output state. Now, Alice and Bob have promised to use a function f which is one of two kinds: either the value of f is constant or balanced. To Eve, it is secret. Alice’s and Bob’s goal is to determine with certainty whether they have chosen a constant or a balanced function. Alice and Bob get one bit if they determine the function f. The speed to get one bit improves by a factor of 2N. This may improve the speed to establish quantum key distribution by a factor of 2N.

Keywords:

Quantum Information Theory, Quantum Computation, Quantum Cryptography

Subject Areas: Applied Physics

1. Introduction

The quantum theory (cf. [1] - [6] ) gives approximate and at times remarkably accurate numerical predictions. Much experimental data approximately fits to the quantum predictions for the past some 100 years. We do not doubt the correctness of the quantum theory. The quantum theory also says new science with respect to information theory. The science is called the quantum information theory [6] . Therefore, the quantum theory gives us very useful another theory in order to create new information science and to explain the handling of raw experimental data in our physical world.

As for the foundations of the quantum theory, Leggett-type non-local variables theory [7] is experimentally investigated [8] - [10] . The experiments report that the quantum theory does not accept Leggett-type non-local variables interpretation. As for the applications of the quantum theory, implementation of a quantum algorithm to solve Deutsch’s problem [11] on a nuclear magnetic resonance quantum computer is reported firstly [12] . Implementation of the Deutsch-Jozsa algorithm on an ion-trap quantum computer is also reported [13] . There are several attempts to use single-photon two-qubit states for quantum computing. Oliveira et al. implement Deutsch’s algorithm with polarization and transverse spatial modes of the electromagnetic field as qubits [14] . Single-photon Bell states are prepared and measured [15] . Also the decoherence-free implementation of Deutsch’s algorithm is reported by using such single-photon and by using two logical qubits [16] . More recently, a one- way based experimental implementation of Deutsch’s algorithm is reported [17] .

The most well known and developed application of quantum cryptography is quantum key distribution (QKD), which is the process of using quantum communication to establish a shared key between two parties without a third party (Eve) learning anything about that key, even if Eve can eavesdrop on all communication between Alice and Bob. This is achieved by Alice encoding the bits of the key as quantum data and sending them to Bob; if Eve tries to learn these bits, the messages will be disturbed and Alice and Bob will notice. The key is then typically used for encrypted communication using classical techniques. For instance, the exchanged key could be used as the seed of the same random number generator both by Alice and Bob.

The security of QKD can be proven mathematically without imposing any restrictions on the abilities of an eavesdropper, something not possible with classical key distribution. This is usually described as “unconditional security”, although there are some minimal assumptions required including that the laws of quantum mechanics apply and that Alice and Bob are able to authenticate each other, i.e. Eve should not be able to impersonate Alice or Bob as otherwise a man-in-the-middle attack would be possible.

To date, the relation between quantum computer and QKD is not reported. The earliest quantum algorithm, the Deutsch-Jozsa algorithm, is representative to show that quantum computation is faster than classical counterpart with a magnitude that grows exponentially with the number of qubits.

Recently, it is discussed that von Neumann’s theory does not meet the Deutsch-Jozsa algorithm [18] . In von Neumann’s theory, control of quantum state and observations of quantum state cannot be existential, simul- taneously. In reference [18] , we propose a solution of the problem. The problem is solved if measurement out- come is.

In this paper, we review the Deutsch-Jozsa algorithm. We suggest that the Deutsch-Jozsa algorithm can be used for improving quantum key distribution. Alice sends input partite uncorrelated state to a black box. Bob measures output state. Now, Alice and Bob has promised to use a function f which is of one of two kinds; either the value of f is constant or balanced. To Eve, it is secret. Alice’s and Bob’s goal is to determine with certainty whether they have chosen a constant or a balanced function. Alice and Bob get one bit if they determine the function f. The speed to get one bit improves by a factor of. This may improve the speed to establish quantum key distribution by a factor of.

2. The Deutsch-Jozsa Algorithm Can Be Used for Quantum Key Distribution

The earliest quantum algorithm, the Deutsch-Jozsa algorithm, is representative to show that quantum computa- tion is faster than classical counterpart with a magnitude that grows exponentially with the number of qubits.

Let us follow the argumentation presented in [6] . The application, known as Deutsch’s problem, may be described as the following game. Alice, in Amsterdam, selects a number x from 0 to, and mails it in a letter to Bob, in Boston. Bob calculates the value of some function

(1)

and replies with the result, which is either 0 or 1. Now, Bob has promised to use a function f which is of one of two kinds; either the value of is constant for all values of x, or else the value of is balanced, that

is, equal to 1 for exactly half of all the possible x, and 0 for the other half. Alice’s goal is to determine with certainty whether Bob has chosen a constant or a balanced function, corresponding with him as little as possible. How fast can she succeed?

In the classical case, Alice may only send Bob one value of x in each letter. At worst, Alice will need to query Bob at least

(2)

times, since she may receive 0 s before finally getting a 1, telling her that Bob’s function is balanced. The best deterministic classical algorithm she can use therefore requires queries. Note that in each letter, Alice sends Bob N bits of information. Furthermore, in this example, physical distance is being used to artificially elevate the cost of calculating, but this is not needed in the general problem, where may be inherently difficult to calculate.

If Bob and Alice were able to exchange qubits, instead of just classical bits, and if Bob agreed to calculate using a unitary transformation, then Alice could achieve her goal in just one correspondence with Bob, using the following algorithm.

Alice has an N qubit register to store her query in, and a single qubit register which she will give to Bob, to store the answer in. She begins by preparing both her query and answer registers in a superposition state. Bob will evaluate using quantum parallelism and leave the result in the answer register. Alice then interferes states in the superposition using a Hadamard transformation (a unitary transformation),

(3)

on the query register, and finishes by performing a suitable measurement to determine whether f was constant or balanced.

Let us follow the quantum states through this algorithm. The input state is

(4)

Here the query register describes the state of N qubits all prepared in the

(5)

state. After the Hadamard transformation on the query register and the Hadamard gate on the answer register we have

(6)

The query register is now a superposition of all values, and the answer register is in an evenly weighted superposition of

(7)

and

(8)

Next, the function f is evaluated (by Bob) using

(9)

giving

(10)

Here

(11)

is the bitwise XOR (exclusive OR) of y and. Alice now has a set of qubits in which the result of Bob’s function evaluation is stored in the amplitude of the qubit superposition state. She now interferes terms in the superposition using a Hadamard transformation on the query register. To determine the result of the Hadamard transformation it helps to first calculate the effect of the Hadamard transformation on a state

(12)

By checking the cases and separately we see that for a single qubit

(13)

Thus

(14)

This can be summarized more succinctly in the very useful equation

(15)

where

(16)

is the bitwise inner product of x and z, modulo 2. Using this equation and (10) we can now evaluate,

(17)

Alice now observes the query register. Note that the absolute value of the amplitude for the state

(18)

is

(19)

Let’s look at the two possible cases―f constant and f balanced―to discern what happens. In the case where f is constant the absolute value of the amplitude for

(20)

is. Because

(21)

is of unit length it follows that all the other amplitudes must be zero, and an observation will yield

(22)

times for all N qubits in the query register. Thus, global measurement outcome is

(23)

If f is balanced then the positive and negative contributions to the absolute value of the amplitude for

(24)

cancel, leaving an amplitude of zero, and a measurement must yield a result other than

(25)

that is,

(26)

on at least one qubit in the query register. Summarizing, if Alice measures all s and global measurement outcome is the function is constant; otherwise the function is balanced.

We suggest that the Deutsch-Jozsa algorithm can be used for quantum key distribution.

• First Alice prepares the qubits in (6) and sends the qubits to Bob.

• Next, Bob picks a random function “f” that is either balanced or constant and Bob applies Equation (9) evolving the qubits to Equation (10). He then sends the N qubit Query register to Alice.

• Finally, Alice applies the Hadamard transformation to each of the qubits and measures. She learns whether f was balanced or constant-Alice and Bob now share a random bit of information (the “type” of).

On safety, a questionable point is left in various ways, but this is a future problem. For example, we can consider the following situation:

Alice has to send the Query (N-qubit) and Answer (1-qubit) registers to Bob. Bob will then apply and send the Query register back to Alice who will apply the second step of the Deutsch-Jozsa algorithm to this register and learn the “type” of. What’s to prevent the attacker Eve from doing this same thing? That is, Eve will capture the N qubits from Bob, apply to the query qubits, and measure. She now learns the type of and thus the key bit. She can then prepare fresh qubits of the form:

if her measurement result was all zeros (f is constant) otherwise (f is balanced).

Alice will then apply (the second part of the Deutsch-Jozsa algorithm) unaware that Eve interfered. Her action will cancel out Eve’s operation and Alice will then measure either all zeros if f is constant or some random non-zero state otherwise. This seems like an undetectable attack. We will need to find a way to counter this in our protocol somehow.

3. Conclusions

In conclusion, we have reviewed the new type of Deutsch-Jozsa algorithm. We have suggested that the Deutsch- Jozsa algorithm can be used for quantum key distribution. Alice has sent input partite uncorrelated state to a black box. Bob has measured output state. Now, Alice and Bob have promised to use a function f which is one of two kinds: either the value of f is constant or balanced. To Eve, it has been secret. Alice’s and Bob’s goal has been to determine with certainty whether they have chosen a constant or a balanced function. Alice and Bob have gotten one bit if they determine the function f. The speed to get one bit has improved by a factor of. This may have improved the speed to establish quantum key distribution by a factor of.

On safety, a questionable point has been left in various ways, but this has been a future problem.

Cite this paper

Koji Nagata,Tadao Nakamura, (2015) The Deutsch-Jozsa Algorithm Can Be Used for Quantum Key Distribution. Open Access Library Journal,02,1-6. doi: 10.4236/oalib.1101798

References

  1. 1. von Neumann, J. (1955) Mathematical Foundations of Quantum Mechanics. Princeton University Press, Princeton.

  2. 2. Feynman, R.P., Leighton, R.B. and Sands, M. (1965) Lectures on Physics. Volume 3, Quantum Mechanics, Addison-Wesley Publishing Company.

  3. 3. Redhead, M. (1989) Incompleteness, Nonlocality, and Realism. 2nd Edition, Clarendon Press, Oxford.

  4. 4. Peres, A. (1993) Quantum Theory: Concepts and Methods. Kluwer Academic, Dordrecht.

  5. 5. Sakurai, J.J. (1995) Modern Quantum Mechanics. Addison-Wesley Publishing Company.

  6. 6. Nielsen, M.A. and Chuang, I.L. (2000) Quantum Computation and Quantum Information. Cambridge University Press, Cambridge.

  7. 7. Leggett, A.J. (2003) Nonlocal Hidden-Variable Theories and Quantum Mechanics: An Incompatibility Theorem. Foundations of Physics, 33, 1469-1493.
    http://dx.doi.org/10.1023/A:1026096313729

  8. 8. Gröblacher, S., Paterek, T., Kaltenbaek, R., Brukner, Č., Żukowski, M., Aspelmeyer, M. and Zeilinger, A. (2007) An Experimental Test of Non-Local Realism. Nature (London), 446, 871-875.
    http://dx.doi.org/10.1038/nature05677

  9. 9. Paterek, T., Fedrizzi, A., Gröblacher, S., Jennewein, T., Żukowski, M., Aspelmeyer, M. and Zeilinger, A. (2007) Experimental Test of Nonlocal Realistic Theories without the Rotational Symmetry Assumption. Physical Review Letters, 99, Article ID: 210406.
    http://dx.doi.org/10.1103/PhysRevLett.99.210406

  10. 10. Branciard, C., Ling, A., Gisin, N., Kurtsiefer, C., Lamas-Linares, A. and Scarani, V. (2007) Experimental Falsification of Leggett’s Nonlocal Variable Model. Physical Review Letters, 99, Article ID: 210407.
    http://dx.doi.org/10.1103/PhysRevLett.99.210407

  11. 11. Deutsch, D. (1985) Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer. Proceedings of the Royal Society of London. Series A, 400, 97.
    http://dx.doi.org/10.1098/rspa.1985.0070

  12. 12. Jones, J.A. and Mosca, M. (1998) Implementation of a Quantum Algorithm on a Nuclear Magnetic Resonance Quantum Computer. The Journal of Chemical Physics, 109, 1648.
    http://dx.doi.org/10.1063/1.476739

  13. 13. Gulde, S., Riebe, M., Lancaster, G.P.T., Becher, C., Eschner, J., Häffner, H., Schmidt-Kaler, F., Chuang, I.L. and Blatt, R. (2003) Implementation of the Deutsch-Jozsa Algorithm on an Ion-Trap Quantum Computer. Nature, 421, 48-50.
    http://dx.doi.org/10.1038/nature01336

  14. 14. de Oliveira, A.N., Walborn, S.P. and Monken, C.H. (2005) Implementing the Deutsch Algorithm with Polarization and Transverse Spatial Modes. Journal of Optics B: Quantum and Semiclassical Optics, 7, 288-292.
    http://dx.doi.org/10.1088/1464-4266/7/9/009

  15. 15. Kim, Y.-H. (2003) Single-Photon Two-Qubit Entangled States: Preparation and Measurement. Physical Review A, 67, Article ID: 040301(R).

  16. 16. Mohseni, M., Lundeen, J.S., Resch, K.J. and Steinberg, A.M. (2003) Experimental Application of Decoherence-Free Subspaces in an Optical Quantum-Computing Algorithm. Physical Review Letters, 91, Article ID: 187903.
    http://dx.doi.org/10.1103/PhysRevLett.91.187903

  17. 17. Tame, M.S., Prevedel, R., Paternostro, M., Böhi, P., Kim, M.S. and Zeilinger, A. (2007) Experimental Realization of Deutsch’s Algorithm in a One-Way Quantum Computer. Physical Review Letters, 98, Article ID: 140501.
    http://dx.doi.org/10.1103/PhysRevLett.98.140501

  18. 18. Nagata, K. and Nakamura, T. (2010) Can von Neumann’s Theory Meet the Deutsch-Jozsa Algorithm? International Journal of Theoretical Physics, 49, 162-170.
    http://dx.doi.org/10.1007/s10773-009-0189-5