The Deutsch–Jozsa algorithm is a deterministic quantum algorithm proposed by David Deutsch and Richard Jozsa in 1992 with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998. Although of little practical use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm.

The Deutsch–Jozsa problem is specifically designed to be easy for a quantum algorithm and hard for any deterministic classical algorithm. It is a black box problem that can be solved efficiently by a quantum computer with no error, whereas a deterministic classical computer would need a exponential number of queries to the black box to solve the problem. More formally, it yields an oracle relative to which EQP, the class of problems that can be solved exactly in polynomial time on a quantum computer, and P are different.

Since the problem is easy to solve on a probabilistic classical computer, it does not yield an oracle separation with BPP, the class of problems that can be solved with bounded error in polynomial time on a probabilistic classical computer. Simon's problem is an example of a problem that yields an oracle separation between BQP and BPP.

Problem statement 
In the Deutsch–Jozsa problem, we are given a black box quantum computer known as an oracle that implements some function: 

 

The function takes n-bit binary values as input and produces either a 0 or a 1 as output for each such value. We are promised that the function is either constant (0 on all inputs or 1 on all inputs) or balanced (1 for exactly half of the input domain and 0 for the other half). The task then is to determine if  is constant or balanced by using the oracle.

Classical solution 
For a conventional deterministic algorithm where  is the number of bits,  evaluations of  will be required in the worst case. To prove that  is constant, just over half the set of inputs must be evaluated and their outputs found to be identical (because the function is guaranteed to be either balanced or constant, not somewhere in between). The best case occurs where the function is balanced and the first two output values are different. For a conventional randomized algorithm, a constant  evaluations of the function suffices to produce the correct answer with a high probability (failing with probability  with ). However,  evaluations are still required if we want an answer that has no possibility of error. The Deutsch-Jozsa quantum algorithm produces an answer that is always correct with a single evaluation of .

History
The Deutsch–Jozsa algorithm generalizes earlier (1985) work by David Deutsch, which provided a solution for the simple case where . 
Specifically, given a boolean function whose input is one bit, , is it constant?

The algorithm, as Deutsch had originally proposed it, was not deterministic. The algorithm was successful with a probability of one half. 
In 1992, Deutsch and Jozsa produced a deterministic algorithm which was generalized to a function which takes  bits for its input. Unlike Deutsch's algorithm, this algorithm required two function evaluations instead of only one.

Further improvements to the Deutsch–Jozsa algorithm were made by Cleve et al., resulting in an algorithm that is both deterministic and requires only a single query of . This algorithm is still referred to as Deutsch–Jozsa algorithm in honour of the groundbreaking techniques they employed.

Algorithm 

For the Deutsch–Jozsa algorithm to work, the oracle computing  from  must be a quantum oracle which does not decohere . It also must not make a copy of , because that would violate the no cloning theorem.

The algorithm begins with the  bit state . That is, the first n bits are each in the state  and the final bit is . A Hadamard transform is applied to each bit to obtain the state

,

where  runs over all -bit strings. We have the function  implemented as a quantum oracle. The oracle maps its input-state  to , where  denotes addition modulo 2. Applying the quantum oracle gives;

.

For each  is either 0 or 1. Testing these two possibilities, we see the above state is equal to

.

At this point the last qubit  may be ignored and the following remains:

.

Next, we will apply the Hadamard transform

 

( is the sum of the bitwise product, where  is addition modulo 2) over the first register to obtain

From this, we can see that the probability for a state  to be measured is

 

The probability of measuring , corresponding to , is

which evaluates to 1 if  is constant (constructive interference) and 0 if  is balanced (destructive interference). In other words, the final measurement will be  (all zeros) if and only if  is constant and will yield some other state if  is balanced.

Deutsch's algorithm
Deutsch's algorithm is a special case of the general Deutsch–Jozsa algorithm where n = 1 in . We need to check the condition . It is equivalent to check  (where  is addition modulo 2, which can also be viewed as a quantum XOR gate implemented as a Controlled NOT gate), if zero, then  is constant, otherwise  is not constant.

We begin with the two-qubit state  and apply a Hadamard transform to each qubit. This yields

We are given a quantum implementation of the function  that maps  to . Applying this function to our current state we obtain

We ignore the last bit and the global phase and therefore have the state

Applying a Hadamard transform to this state we have

 if and only if we measure  and  if and only if we measure . So with certainty we know whether  is constant or balanced.

See also
Bernstein–Vazirani algorithm

References

External links
Deutsch's lecture about the Deutsch-Jozsa algorithm

Quantum algorithms
도이치–조사 알고리듬은 1992년 데이비드 도이치와 리처드 조사가 제안하고 1998년 리차드 클리브, 아서 에케르트, 키아라 맥카벨로 및 마이클 모스카가 개선한 결정론적 양자 알고리듬이다. 현재 실용성은 거의 없지만, 가능한 결정론적 고전 알고리듬보다 기하급수적으로 빠른 양자 알고리듬의 첫 번째 예 중 하나로 역사적인 의미가 있다.

도이치-조사 알고리듬으로 푸는 문제는, 양자 알고리듬에는 쉽고 결정적 고전 알고리듬에는 어렵도록 의도적으로 설계된 문제이다. 이는 양자 컴퓨터로 오류 없이 효율적으로 해결할 수 있는 블랙박스 문제인 반면, 결정론적 고전 컴퓨터는 문제를 해결하기 위해 블랙박스에 대한 기하급수적인 쿼리가 필요하다. 보다 자세히 설명하면, 양자 컴퓨터에서 다항식 시간 내에 정확하게 해결할 수 있는 문제 클래스인 EQP와 P가 다른 것과 관련하여 오라클을 생성한다.

이 문제는 확률적 고전 컴퓨터에서 해결하기 쉽기 때문에 확률적 고전 컴퓨터에서 다항식 시간의 유계 오류로 해결할 수 있는 문제 클래스인 BPP와 오라클 분리를 생성하지 않는다. 반면에, 사이먼 문제는 BQP와 BPP 사이에 오라클이 분리되는 문제의 예이다.

문제 설명 
도이치-조사 문제에서 다음 함수를 구현하는 오라클로 알려진 블랙박스 양자 컴퓨터가 주어져 있다:

이 함수는 비트 이진수를  또는 로 보낸다. 이 함수는 상수 함수(정의역 전체에서  또는 정의역 전체에서 )이거나 균형 함수 (정확히 정의역의 원소들 절반에 대해 , 나머지 절반에 대해 )이다. 이때, 도이치-조사 문제는, 오라클을 사용하여 가 상수 함수인지 균형 함수인지 판단하는 것이다.

고전적인 해 
기존의 결정론적 알고리듬의 경우  비트에 대해, 최악의 경우 를 계산해야하는 횟수는 지수함수적으로 증가한다. 반면에 함수가 균형 함수이고 처음 두 출력 값이 다른 경우 최상의 경우가 발생한다. 기존의 무작위 알고리듬의 경우, 충분히 큰 에 대해 를 번 계산하면 높은 확률로 정답을 생성한다.(에 대해 확률로 실패). 하지만, 오류 가능성이 없는 답을 원할 경우 필요한  계산의 횟수는 여전히 지수함수적이다. 그러나, 도이치-조사 양자 알고리듬은 에 대한 계산 한 번으로 항상 올바른 답을 내놓는다.

역사 
도이치-조사 알고리듬은 인 경우에만 해를 제공했던 다음 데이비드 도이치의 초기(1985)작업"입력이 1비트인 불 함수가 주어졌을 때, 이 함수가 상수 함수인가?"

을 일반화 하였다. 도이치가 원래 제안한 알고리듬은 사실 결정론적이지 않았다. 알고리듬은 절반의 확률로 성공했다. 1992년에 도이치와 조사는 비트 입력을 가진 함수로 일반화된 결정적 알고리듬을 만들었다. 도이치의 알고리듬과 달리, 이 알고리듬에는 하나가 아닌 두 개의 함수 계산이 필요했다.

도이치-조사 알고리듬에 대한 추가 개선 사항은 클레브와 다른 사람들에 의해 이루어졌다. 이들은 도이치-조사 알고리듬을 결정론적이며 의 쿼리 하나만 필요한 알고리듬으로 만들었다. 그러나 알고리듬의 이름은 도이치와 조사가 사용한 획기적인 방법을 기리기 위해 여전히 도이치-조사 알고리듬이라고 한다.

연산 
도이치-조사 알고리듬이 작동하려면 에서  값을 계산하는 오라클 계산은  결어긋남이 없는 양자 오라클이어야 한다. 또한 의 사본을 만들면 안된다. 만약 복제가 된다면 양자역학의 복제 불가능성 정리를 위반 하기 때문이다.

알고리듬은  큐비트가 인 상태에서 시작한다. 즉, 처음  큐비트는 각각 상태 에 있고 마지막 큐비트는 인 상태이다. 그 다음, 각 큐비트에 아다마흐 변환을 적용 해서 다음 상태를 얻는다:

  .

이때, 는 양자 오라클로 구현되었다고 가정한다. 이 오라클은 상태 를 로 보낸다. 여기서, 는 를 법으로 하는 덧셈을 나타낸다. 여기에 양자 오라클을 적용하면 다음을 얻는다:

  .

한편, 와 는 각각  또는 이다. 이 두 가지 가능성을 시험하면 위의 상태가 다음과 같다는 것을 알 수 있다.

 .

이 때, 마지막 큐비트 는 무시할 수 있으며,

 

부분만 고려하면 된다

다음으로, 첫 번째 큐비트에 아다마흐 변환을 적용하여

 

(여기서 는 비트 곱들의 합이다.) 다음을 얻는다:

 

이것으로부터 우리는 상태 에 대한 확률이

 

로 측정됨을 알 수 있다.

에 해당하는 을 측정할 확률은

 

이다.

가 상수(보강 간섭)이면 위 상태는 로 측정 되고, 균형 함수(상쇄 간섭)이면 로 측정 된다. 즉, 오직 가 상수 함수일 때 만 최종 측정 값이 (모두 )이다.

도이치 알고리듬 
도이치 알고리듬은 일반 도이치-조사 알고리듬의 에서  일 때에 해당한다. 인지 확인 하는 것과  값을 확인하는 것은 같다.  (여기서,  제어된 NOT 게이트로 구현되었고 양자 XOR 게이트로 볼 수도 있는 를 법으로 하는 덧셈이다.) 이 값이 이면 는 상수 함수고, 이면 는 균형 함수다.

 큐비트 상태 에서 시작한다. 아다마흐 변환을 각 큐비트에 적용해서 다음을 얻는다:

 

를 로 보내는 함수 의 양자 구현이 주어졌다고 가정한다. 이를 현재 상태에 적용하면

 
 
 

를 얻는다.

마지막 큐비트와 전체 페이즈를 무시하므로 다음 항만 고려한다:

 

이 상태에 아다마흐 변환을 적용하면

 
 

여기서, 임과 을 측정하는 것이 동치이고 임과  를 측정하는것이 동치이다. 따라서 확실하게 가 상수 함수인지 아닌지 알 수 있다.

같이 보기 
 번스타인-바지라니 알고리듬

각주

외부 링크 
 도이치-조사 알고리듬에 대한 도이치의 강의

양자 알고리즘