Deutsch–Jozsa algorithm

<h2 id="problem-statement">Problem statement</h2>
In the Deutsch–Jozsa problem, we are given a black box quantum computer known as an <a href="/facts/Oracle_machine/6ScMuvvY">oracle</a> that implements some function: 

 
 
 
 f
 :
 {
 0
 ,
 1
 
 }
 
 n
 
 
 →
 {
 0
 ,
 1
 }
 
 
 {\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}
 
 
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 <a href="/facts/Promise_problem/rY0vsSjA">promised</a> that the function is either <a href="/facts/Constant_function/BmPx6dn7">constant</a> (0 on all inputs or 1 on all inputs) or balanced (1 for exactly half of the input <a href="/facts/Function_domain/FQvoeUpX">domain</a> and 0 for the other half).<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> The task then is to determine if 
 
 
 
 f
 
 
 {\displaystyle f}
 
 is constant or balanced by using the oracle.

<h2 id="classical-solution">Classical solution</h2>
For a conventional <a href="/facts/Deterministic/NhvNlAbe">deterministic</a> algorithm where 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is the number of bits, 
 
 
 
 
 2
 
 n
 −
 1
 
 
 +
 1
 
 
 {\displaystyle 2^{n-1}+1}
 
 evaluations of 
 
 
 
 f
 
 
 {\displaystyle f}
 
 will be required in the worst case. To prove that 
 
 
 
 f
 
 
 {\displaystyle f}
 
 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 <a href="/facts/Randomized_algorithm/Fngl1zgk">randomized algorithm</a>, a constant 
 
 
 
 k
 
 
 {\displaystyle k}
 
 evaluations of the function suffices to produce the correct answer with a high probability (failing with probability 
 
 
 
 ϵ
 ≤
 1
 
 /
 
 
 2
 
 k
 
 
 
 
 {\displaystyle \epsilon \leq 1/2^{k}}
 
 with 
 
 
 
 k
 ≥
 1
 
 
 {\displaystyle k\geq 1}
 
). However, 
 
 
 
 k
 =
 
 2
 
 n
 −
 1
 
 
 +
 1
 
 
 {\displaystyle k=2^{n-1}+1}
 
 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 
 
 
 
 f
 
 
 {\displaystyle f}
 
.

<h2 id="history">History</h2>
The Deutsch–Jozsa algorithm generalizes earlier (1985) work by David Deutsch, which provided a solution for the simple case where 
 
 
 
 n
 =
 1
 
 
 {\displaystyle n=1}
 
. 
Specifically, finding out if a given <a href="/facts/Boolean_function/uT7E8pqC">Boolean function</a> whose input is one bit, 
 
 
 
 f
 :
 {
 0
 ,
 1
 }
 →
 {
 0
 ,
 1
 }
 
 
 {\displaystyle f:\{0,1\}\to \{0,1\}}
 
, is constant.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
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 
 
 
 
 n
 
 
 {\displaystyle n}
 
 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.,<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> resulting in an algorithm that is both deterministic and requires only a single query of 
 
 
 
 f
 
 
 {\displaystyle f}
 
. This algorithm is still referred to as Deutsch–Jozsa algorithm in honour of the groundbreaking techniques they employed.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="algorithm">Algorithm</h2>
For the Deutsch–Jozsa algorithm to work, the oracle computing 
 
 
 
 f
 (
 x
 )
 
 
 {\displaystyle f(x)}
 
 from 
 
 
 
 x
 
 
 {\displaystyle x}
 
 must be a quantum oracle which does not <a href="/facts/Quantum_decoherence/mngM3rxy">decohere</a> 
 
 
 
 x
 
 
 {\displaystyle x}
 
. In its computation, it cannot make a copy of 
 
 
 
 x
 
 
 {\displaystyle x}
 
, because that would violate the <a href="/facts/No_cloning_theorem/cLYH4pQE">no cloning theorem</a>. The point of view of the Deutsch-Jozsa algorithm of 
 
 
 
 f
 
 
 {\displaystyle f}
 
 as an oracle means that it does not matter what the oracle does, since it just has to perform its promised transformation.

The algorithm begins with the 
 
 
 
 n
 +
 1
 
 
 {\displaystyle n+1}
 
 bit state 
 
 
 
 
 |
 
 0
 
 ⟩
 
 ⊗
 n
 
 
 
 |
 
 1
 ⟩
 
 
 {\displaystyle |0\rangle ^{\otimes n}|1\rangle }
 
. That is, the first n bits are each in the state 
 
 
 
 
 |
 
 0
 ⟩
 
 
 {\displaystyle |0\rangle }
 
 and the final bit is 
 
 
 
 
 |
 
 1
 ⟩
 
 
 {\displaystyle |1\rangle }
 
. A <a href="/facts/Quantum_logic_gate/EFV5sPCU">Hadamard gate</a> is applied to each bit to obtain the state

 
 
 
 
 
 1
 
 
 2
 
 n
 +
 1
 
 
 
 
 
 
 ∑
 
 x
 =
 0
 
 
 
 2
 
 n
 
 
 −
 1
 
 
 
 |
 
 x
 ⟩
 (
 
 |
 
 0
 ⟩
 −
 
 |
 
 1
 ⟩
 )
 ,
 
 
 {\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle ),}

where 
 
 
 
 x
 
 
 {\displaystyle x}
 
 runs over all 
 
 
 
 n
 
 
 {\displaystyle n}
 
-bit strings, which each may be represented by a number from 
 
 
 
 0
 
 
 {\displaystyle 0}
 
 to 
 
 
 
 
 2
 
 n
 
 
 −
 1
 
 
 {\displaystyle 2^{n}-1}
 
. We have the function 
 
 
 
 f
 
 
 {\displaystyle f}
 
 implemented as a quantum oracle. The oracle maps its input state 
 
 
 
 
 |
 
 x
 ⟩
 
 |
 
 y
 ⟩
 
 
 {\displaystyle |x\rangle |y\rangle }
 
 to 
 
 
 
 
 |
 
 x
 ⟩
 
 |
 
 y
 ⊕
 f
 (
 x
 )
 ⟩
 
 
 {\displaystyle |x\rangle |y\oplus f(x)\rangle }
 
, where 
 
 
 
 ⊕
 
 
 {\displaystyle \oplus }
 
 denotes addition modulo 2. Applying the quantum oracle gives;

 
 
 
 
 
 1
 
 
 2
 
 n
 +
 1
 
 
 
 
 
 
 ∑
 
 x
 =
 0
 
 
 
 2
 
 n
 
 
 −
 1
 
 
 
 |
 
 x
 ⟩
 (
 
 |
 
 0
 ⊕
 f
 (
 x
 )
 ⟩
 −
 
 |
 
 1
 ⊕
 f
 (
 x
 )
 ⟩
 )
 .
 
 
 {\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\oplus f(x)\rangle -|1\oplus f(x)\rangle ).}

For each 
 
 
 
 x
 ,
 f
 (
 x
 )
 
 
 {\displaystyle x,f(x)}
 
 is either 0 or 1. Testing these two possibilities, we see the above state is equal to

 
 
 
 
 
 1
 
 
 2
 
 n
 +
 1
 
 
 
 
 
 
 ∑
 
 x
 =
 0
 
 
 
 2
 
 n
 
 
 −
 1
 
 
 (
 −
 1
 
 )
 
 f
 (
 x
 )
 
 
 
 |
 
 x
 ⟩
 (
 
 |
 
 0
 ⟩
 −
 
 |
 
 1
 ⟩
 )
 .
 
 
 {\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle ).}

At this point the last qubit 
 
 
 
 
 
 
 
 |
 
 0
 ⟩
 −
 
 |
 
 1
 ⟩
 
 
 2
 
 
 
 
 
 {\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}
 
 may be ignored and the following remains:

 
 
 
 
 
 1
 
 
 2
 
 n
 
 
 
 
 
 
 ∑
 
 x
 =
 0
 
 
 
 2
 
 n
 
 
 −
 1
 
 
 (
 −
 1
 
 )
 
 f
 (
 x
 )
 
 
 
 |
 
 x
 ⟩
 .
 
 
 {\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle .}

Next, we will have each qubit go through a <a href="/facts/Quantum_logic_gate/EFV5sPCU">Hadamard gate</a>. The total transformation over all 
 
 
 
 n
 
 
 {\displaystyle n}
 
 qubits can be expressed with the following identity:

 
 
 
 
 H
 
 ⊗
 n
 
 
 
 |
 
 k
 ⟩
 =
 
 
 1
 
 
 2
 
 n
 
 
 
 
 
 
 ∑
 
 j
 =
 0
 
 
 
 2
 
 n
 
 
 −
 1
 
 
 (
 −
 1
 
 )
 
 k
 ⋅
 j
 
 
 
 |
 
 j
 ⟩
 
 
 {\displaystyle H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle }

(
 
 
 
 j
 ⋅
 k
 =
 
 j
 
 0
 
 
 
 k
 
 0
 
 
 ⊕
 
 j
 
 1
 
 
 
 k
 
 1
 
 
 ⊕
 ⋯
 ⊕
 
 j
 
 n
 −
 1
 
 
 
 k
 
 n
 −
 1
 
 
 
 
 {\displaystyle j\cdot k=j_{0}k_{0}\oplus j_{1}k_{1}\oplus \cdots \oplus j_{n-1}k_{n-1}}
 
 is the sum of the bitwise product). This results in

 
 
 
 
 
 1
 
 
 2
 
 n
 
 
 
 
 
 
 ∑
 
 x
 =
 0
 
 
 
 2
 
 n
 
 
 −
 1
 
 
 (
 −
 1
 
 )
 
 f
 (
 x
 )
 
 
 
 [
 
 
 
 1
 
 
 2
 
 n
 
 
 
 
 
 
 ∑
 
 y
 =
 0
 
 
 
 2
 
 n
 
 
 −
 1
 
 
 
 
 
 (
 
 −
 1
 
 )
 
 
 
 x
 ⋅
 y
 
 
 
 |
 
 y
 ⟩
 
 ]
 
 =
 
 ∑
 
 y
 =
 0
 
 
 
 2
 
 n
 
 
 −
 1
 
 
 
 [
 
 
 
 1
 
 2
 
 n
 
 
 
 
 
 ∑
 
 x
 =
 0
 
 
 
 2
 
 n
 
 
 −
 1
 
 
 (
 −
 1
 
 )
 
 f
 (
 x
 )
 
 
 (
 −
 1
 
 )
 
 x
 ⋅
 y
 
 
 
 ]
 
 
 |
 
 y
 ⟩
 .
 
 
 {\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{y=0}^{2^{n}-1}{\left(-1\right)}^{x\cdot y}|y\rangle \right]=\sum _{y=0}^{2^{n}-1}\left[{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle .}

From this, we can see that the probability for a state 
 
 
 
 k
 
 
 {\displaystyle k}
 
 to be measured is

 
 
 
 
 
 |
 
 
 
 1
 
 2
 
 n
 
 
 
 
 
 ∑
 
 x
 =
 0
 
 
 
 2
 
 n
 
 
 −
 1
 
 
 
 
 
 (
 
 −
 1
 
 )
 
 
 
 f
 (
 x
 )
 
 
 
 
 
 (
 
 −
 1
 
 )
 
 
 
 x
 ⋅
 k
 
 
 
 |
 
 
 2
 
 
 
 
 {\displaystyle \left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}{\left(-1\right)}^{f(x)}{\left(-1\right)}^{x\cdot k}\right|^{2}}

The probability of measuring 
 
 
 
 k
 =
 0
 
 
 {\displaystyle k=0}
 
, corresponding to 
 
 
 
 
 |
 
 0
 
 ⟩
 
 ⊗
 n
 
 
 
 
 {\displaystyle |0\rangle ^{\otimes n}}
 
, is

 
 
 
 
 
 |
 
 
 
 
 1
 
 2
 
 n
 
 
 
 
 
 ∑
 
 x
 =
 0
 
 
 
 2
 
 n
 
 
 −
 1
 
 
 (
 −
 1
 
 )
 
 f
 (
 x
 )
 
 
 
 
 
 |
 
 
 
 2
 
 
 
 
 {\displaystyle {\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}}

which evaluates to 1 if 
 
 
 
 f
 (
 x
 )
 
 
 {\displaystyle f(x)}
 
 is constant (<a href="/facts/Constructive_interference/lI5f78I4">constructive interference</a>) and 0 if 
 
 
 
 f
 (
 x
 )
 
 
 {\displaystyle f(x)}
 
 is balanced (<a href="/facts/Destructive_interference/lI5f78I4">destructive interference</a>). In other words, the final measurement will be 
 
 
 
 
 |
 
 0
 
 ⟩
 
 ⊗
 n
 
 
 
 
 {\displaystyle |0\rangle ^{\otimes n}}
 
 (all zeros) if and only if 
 
 
 
 f
 (
 x
 )
 
 
 {\displaystyle f(x)}
 
 is constant and will yield some other state if 
 
 
 
 f
 (
 x
 )
 
 
 {\displaystyle f(x)}
 
 is balanced.

<h2 id="deutschs-algorithm">Deutsch's algorithm</h2>
Deutsch's algorithm is a special case of the general Deutsch–Jozsa algorithm where n = 1 in 
 
 
 
 f
 :
 {
 0
 ,
 1
 
 }
 
 n
 
 
 →
 {
 0
 ,
 1
 }
 
 
 {\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}
 
. We need to check the condition 
 
 
 
 f
 (
 0
 )
 =
 f
 (
 1
 )
 
 
 {\displaystyle f(0)=f(1)}
 
. It is equivalent to check 
 
 
 
 f
 (
 0
 )
 ⊕
 f
 (
 1
 )
 
 
 {\displaystyle f(0)\oplus f(1)}
 
 (where 
 
 
 
 ⊕
 
 
 {\displaystyle \oplus }
 
 is addition modulo 2, which can also be viewed as a quantum <a href="/facts/XOR_gate/WSfdqTcA">XOR gate</a> implemented as a <a href="/facts/Controlled_NOT_gate/hP1y4K6d">Controlled NOT gate</a>), if zero, then 
 
 
 
 f
 
 
 {\displaystyle f}
 
 is constant, otherwise 
 
 
 
 f
 
 
 {\displaystyle f}
 
 is not constant.
We begin with the two-qubit state 
 
 
 
 
 |
 
 0
 ⟩
 
 |
 
 1
 ⟩
 
 
 {\displaystyle |0\rangle |1\rangle }
 
 and apply a <a href="/facts/Quantum_logic_gate/EFV5sPCU">Hadamard gate</a> to each qubit. This yields

1
            2
          
        
        (
        
          |
        
        0
        ⟩
        +
        
          |
        
        1
        ⟩
        )
        (
        
          |
        
        0
        ⟩
        −
        
          |
        
        1
        ⟩
        )
        .
      
    
    {\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).}

We are given a quantum implementation of the function 
 
 
 
 f
 
 
 {\displaystyle f}
 
 that maps 
 
 
 
 
 |
 
 x
 ⟩
 
 |
 
 y
 ⟩
 
 
 {\displaystyle |x\rangle |y\rangle }
 
 to 
 
 
 
 
 |
 
 x
 ⟩
 
 |
 
 f
 (
 x
 )
 ⊕
 y
 ⟩
 
 
 {\displaystyle |x\rangle |f(x)\oplus y\rangle }
 
. Applying this function to our current state we obtain

1
                    2
                  
                
                (
                
                  |
                
                0
                ⟩
                (
                
                  |
                
                f
                (
                0
                )
                ⊕
                0
                ⟩
                −
                
                  |
                
                f
                (
                0
                )
                ⊕
                1
                ⟩
                )
                +
                
                  |
                
                1
                ⟩
                (
                
                  |
                
                f
                (
                1
                )
                ⊕
                0
                ⟩
                −
                
                  |
                
                f
                (
                1
                )
                ⊕
                1
                ⟩
                )
                )
              
            
            
              
              
                
                =
                
                  
                    1
                    2
                  
                
                (
                (
                −
                1
                
                  )
                  
                    f
                    (
                    0
                    )
                  
                
                
                  |
                
                0
                ⟩
                (
                
                  |
                
                0
                ⟩
                −
                
                  |
                
                1
                ⟩
                )
                +
                (
                −
                1
                
                  )
                  
                    f
                    (
                    1
                    )
                  
                
                
                  |
                
                1
                ⟩
                (
                
                  |
                
                0
                ⟩
                −
                
                  |
                
                1
                ⟩
                )
                )
              
            
            
              
              
                
                =
                (
                −
                1
                
                  )
                  
                    f
                    (
                    0
                    )
                  
                
                
                  
                    1
                    2
                  
                
                
                  (
                  
                    
                      |
                    
                    0
                    ⟩
                    +
                    (
                    −
                    1
                    
                      )
                      
                        f
                        (
                        0
                        )
                        ⊕
                        f
                        (
                        1
                        )
                      
                    
                    
                      |
                    
                    1
                    ⟩
                  
                  )
                
                (
                
                  |
                
                0
                ⟩
                −
                
                  |
                
                1
                ⟩
                )
                .
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}&{\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))\\&={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))\\&=(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle ).\end{aligned}}}

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

1
            
              2
            
          
        
        (
        
          |
        
        0
        ⟩
        +
        (
        −
        1
        
          )
          
            f
            (
            0
            )
            ⊕
            f
            (
            1
            )
          
        
        
          |
        
        1
        ⟩
        )
        .
      
    
    {\displaystyle {\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ).}

Applying a Hadamard gate to this state we have

1
                    2
                  
                
                (
                
                  |
                
                0
                ⟩
                +
                
                  |
                
                1
                ⟩
                +
                (
                −
                1
                
                  )
                  
                    f
                    (
                    0
                    )
                    ⊕
                    f
                    (
                    1
                    )
                  
                
                
                  |
                
                0
                ⟩
                −
                (
                −
                1
                
                  )
                  
                    f
                    (
                    0
                    )
                    ⊕
                    f
                    (
                    1
                    )
                  
                
                
                  |
                
                1
                ⟩
                )
              
            
            
              
              
                
                =
                
                  
                    1
                    2
                  
                
                (
                (
                1
                +
                (
                −
                1
                
                  )
                  
                    f
                    (
                    0
                    )
                    ⊕
                    f
                    (
                    1
                    )
                  
                
                )
                
                  |
                
                0
                ⟩
                +
                (
                1
                −
                (
                −
                1
                
                  )
                  
                    f
                    (
                    0
                    )
                    ⊕
                    f
                    (
                    1
                    )
                  
                
                )
                
                  |
                
                1
                ⟩
                )
                .
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}&{\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )\\&={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).\end{aligned}}}

f
 (
 0
 )
 ⊕
 f
 (
 1
 )
 =
 0
 
 
 {\displaystyle f(0)\oplus f(1)=0}
 
 if and only if we measure 
 
 
 
 
 |
 
 0
 ⟩
 
 
 {\displaystyle |0\rangle }
 
 and 
 
 
 
 f
 (
 0
 )
 ⊕
 f
 (
 1
 )
 =
 1
 
 
 {\displaystyle f(0)\oplus f(1)=1}
 
 if and only if we measure 
 
 
 
 
 |
 
 1
 ⟩
 
 
 {\displaystyle |1\rangle }
 
. So with certainty we know whether 
 
 
 
 f
 (
 x
 )
 
 
 {\displaystyle f(x)}
 
 is constant or balanced.

<h2 id="deutschjozsa-algorithm-qiskit-implementation">Deutsch–Jozsa algorithm Qiskit implementation</h2>
The quantum circuit shown here is from <a href="https://learning.quantum.ibm.com/course/fundamentals-of-quantum-algorithms/quantum-query-algorithms#the-deutsch-jozsa-algorithm">a simple example of how the Deutsch–Jozsa algorithm can be implemented in Python</a> using <a href="/facts/Qiskit/ND9psKTQ">Qiskit</a>, an open-source quantum computing software development framework by IBM.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Bernstein%E2%80%93Vazirani_algorithm/PbQMTQm0">Bernstein–Vazirani algorithm</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.quiprocone.org/Protected/Lecture_5.htm">Deutsch's lecture about the Deutsch-Jozsa algorithm</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">David Deutsch & Richard Jozsa (1992). "Rapid solutions of problems by quantum computation". Proceedings of the Royal Society of London A. 439 (1907): 553–558. Bibcode:1992RSPSA.439..553D. CiteSeerX 10.1.1.655.5997. doi:10.1098/rspa.1992.0167. S2CID 121702767. <a href="/wiki/David_Deutsch" target="_blank">/wiki/David_Deutsch</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">R. Cleve; A. Ekert; C. Macchiavello; M. Mosca (1998). "Quantum algorithms revisited". Proceedings of the Royal Society of London A. 454 (1969): 339–354. arXiv:quant-ph/9708016. Bibcode:1998RSPSA.454..339C. doi:10.1098/rspa.1998.0164. S2CID 16128238. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Simon, Daniel (November 1994). "On the power of quantum computation". Proceedings 35th Annual Symposium on Foundations of Computer Science. pp. 116–123. doi:10.1109/SFCS.1994.365701. ISBN 0-8186-6580-7. S2CID 7457814. <a href="0-8186-6580-7" target="_blank">0-8186-6580-7</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Johansson, N.; Larsson, JÅ. (2017). "Efficient classical simulation of the Deutsch–Jozsa and Simon's algorithms". Quantum Inf Process (2017). 16 (9): 233. arXiv:1508.05027. Bibcode:2017QuIP...16..233J. doi:10.1007/s11128-017-1679-7. S2CID 28670540. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">David Deutsch & Richard Jozsa (1992). "Rapid solutions of problems by quantum computation". Proceedings of the Royal Society of London A. 439 (1907): 553–558. Bibcode:1992RSPSA.439..553D. CiteSeerX 10.1.1.655.5997. doi:10.1098/rspa.1992.0167. S2CID 121702767. <a href="/wiki/David_Deutsch" target="_blank">/wiki/David_Deutsch</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">David Deutsch (1985). "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer". Proceedings of the Royal Society of London A. 400 (1818): 97–117. Bibcode:1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382. doi:10.1098/rspa.1985.0070. S2CID 1438116. <a href="/wiki/David_Deutsch" target="_blank">/wiki/David_Deutsch</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">R. Cleve; A. Ekert; C. Macchiavello; M. Mosca (1998). "Quantum algorithms revisited". Proceedings of the Royal Society of London A. 454 (1969): 339–354. arXiv:quant-ph/9708016. Bibcode:1998RSPSA.454..339C. doi:10.1098/rspa.1998.0164. S2CID 16128238. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">R. Cleve; A. Ekert; C. Macchiavello; M. Mosca (1998). "Quantum algorithms revisited". Proceedings of the Royal Society of London A. 454 (1969): 339–354. arXiv:quant-ph/9708016. Bibcode:1998RSPSA.454..339C. doi:10.1098/rspa.1998.0164. S2CID 16128238. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
</ol>

Deutsch–Jozsa algorithm open-in-new

Deutsch–Jozsa algorithm