도이치–조사 알고리듬

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

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

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

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

f\colon\{0,1\}^n\rightarrow \{0,1\}

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

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

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

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

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

## 연산
도이치-조사 알고리듬이 작동하려면 x에서 f(x) 값을 계산하는 오라클 계산은 x 결어긋남이 없는 양자 오라클이어야 한다. 또한 x의 사본을 만들면 안된다. 만약 복제가 된다면 양자역학의 복제 불가능성 정리를 위반 하기 때문이다.
오른쪽|섬네일|400x400픽셀| 도이치-조사 알고리듬 양자 회로
알고리듬은 n+1 큐비트가 |0\rangle^{\otimes n} |1\rangle 인 상태에서 시작한다. 즉, 처음 n 큐비트는 각각 상태 |0\rangle 에 있고 마지막 큐비트는 |1\rangle 인 상태이다. 그 다음, 각 큐비트에 아다마흐 변환을 적용 해서 다음 상태를 얻는다:

: \frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} |x\rangle (|0\rangle - |1\rangle ) .

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

: \frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} |x\rangle (|0\oplus f(x)\rangle - |1\oplus f(x)\rangle ) .

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

: \frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} (-1)^{f(x)} |x\rangle (|0\rangle - |1\rangle ).

이 때, 마지막 큐비트 \frac{|0\rangle - |1\rangle}{\sqrt{2}}는 무시할 수 있으며,

: \frac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^n-1} (-1)^{f(x)} |x\rangle

부분만 고려하면 된다

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

: H^{\otimes n} |k\rangle = \frac{1}{\sqrt{2^n}} \sum_{j = 0}^{2^n - 1} (-1)^{k \cdot j} |j\rangle

(여기서 k\cdot j는 비트 곱들의 합j_0 k_0\oplus j_1 k_1\oplus\cdots\oplus j_{n-1} k_{n-1} 이다.) 다음을 얻는다:

: \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}(-1)^{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. 

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

: \left|\frac{1}{2^n} \sum_{x=0}^{2^n-1}(-1)^{f(x)} (-1)^{x\cdot k}\right|^2

로 측정됨을 알 수 있다.

|0\rangle^{\otimes n}에 해당하는 k = 0 을 측정할 확률은

: \bigg|\frac{1}{2^n}\sum_{x=0}^{2^n-1}(-1)^{f(x)}\bigg|^2

이다.

f(x)가 상수(보강 간섭)이면 위 상태는 1로 측정 되고, 균형 함수(상쇄 간섭)이면 0로 측정 된다. 즉, 오직 f(x)가 상수 함수일 때 만 최종 측정 값이 |0\rangle^{\otimes n}(모두 0)이다.

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

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

: \frac{1}{2}(|0\rangle + |1\rangle)(|0\rangle - |1\rangle).

|x\rangle |y\rangle를 |x\rangle |f(x)\oplus y\rangle로 보내는 함수 f의 양자 구현이 주어졌다고 가정한다. 이를 현재 상태에 적용하면

: \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)

를 얻는다.

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

: \frac{1}{\sqrt 2}(|0\rangle + (-1)^{f(0)\oplus f(1)}|1\rangle).

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

: \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).

여기서, f(0)\oplus f(1)=0임과 |0\rangle을 측정하는 것이 동치이고 f(0)\oplus f(1)=1임과  |1\rangle를 측정하는것이 동치이다. 따라서 확실하게 f(x)가 상수 함수인지 아닌지 알 수 있다.

## 도이치–조사 알고리즘 Qiskit 구현
다음은 IBM에서 개발한 오픈 소스 양자 컴퓨팅 소프트웨어 프레임워크인 Qiskit을 사용하여 파이썬으로 도이치–조사 알고리즘을 구현한 간단한 예시입니다. 이 알고리즘이 실제 양자 회로로 어떻게 변환되는지 단계별로 살펴보겠습니다.

### 1. 필요한 라이브러리 불러들이기

```python3
from qiskit import QuantumCircuit, transpile
from qiskit_aer import Aer
```


### 2. 오라클을 생성하는 도움 함수 정의

```python3
def create_constant_oracle(n_qubits, output):
    """
    'constant' 오라클을 생성합니다.

    `output`이 0이면 오라클은 항상 0을 반환합니다.
    `output`이 1이면 오라클은 항상 1을 반환합니다.

    매개변수:
        n_qubits (int): 입력 큐비트의 수.
        output (int): 함수가 반환하는 상수값 (0 또는 1).

    반환값:
        QuantumCircuit: constant 오라클을 구현하는 양자 회로.
    """
    oracle = QuantumCircuit(n_qubits + 1)

    # 오라클이 항상 1을 출력해야 한다면,
    # X 게이트(큐비트에서 NOT 게이트로 생각할 수 있음)를 사용하여 "output" 큐비트를 뒤집습니다.
    if output == 1:
        oracle.x(n_qubits)

    return oracle

def create_balanced_oracle(n_qubits):
    """
    'balanced' 오라클을 생성합니다.

    전체 입력 비트 패턴 중 절반에 대해 0을, 나머지 절반에 대해 1을 반환합니다.

    연습을 위해, 첫 번째 입력 큐비트를 제어 큐비트로 사용하여
    출력 큐비트를 뒤집는 간단한 balanced 함수를 구현합니다.

    매개변수:
        n_qubits (int): 입력 큐비트의 수.

    반환값:
        QuantumCircuit: balanced 오라클을 구현하는 양자 회로.
    """
    oracle = QuantumCircuit(n_qubits + 1)

    # 간단한 동작을 설정합니다: 첫 번째 큐비트가 1이면 출력 큐비트를 뒤집습니다.
    # 이 동작으로 가능한 입력의 절반에 대해서 출력이 바뀝니다.
    oracle.cx(0, n_qubits)

    return oracle
```


### 3. 도이치–조사 회로를 조립하는 함수

```python3
def deutsch_jozsa_circuit(oracle, n_qubits):
    """
    도이치–조자 알고리즘의 전체 양자 회로를 조립합니다.

    이 회로는 다음 단계를 수행합니다:
    1. 모든 '입력' 큐비트를 |0> 상태로 시작합니다.
    2. '출력' 큐비트를 |1> 상태로 시작합니다.
    3. 모든 큐비트에 하다마드 게이트를 적용합니다.
    4. 오라클을 적용합니다.
    5. 입력 큐비트에 다시 하다마드 게이트를 적용합니다.
    6. 입력 큐비트를 측정합니다.

    매개변수:
        oracle (QuantumCircuit): '미스터리' 함수 f(x)를 인코딩한 회로.
        n_qubits (int): 입력 큐비트의 수.

    반환값:
        QuantumCircuit: 실행할 준비가 된 완성된 도이치–조자 회로.
    """
    # 총 n_qubits(입력) + 1(출력) 큐비트
    dj_circuit = QuantumCircuit(n_qubits + 1, n_qubits)

    # 1. 입력 큐비트는 이미 |0> 상태입니다.
    # 2. 출력 큐비트를 |1>로 설정합니다. 이를 위해 X 게이트를 적용합니다.
    dj_circuit.x(n_qubits)

    # 3. 모든 큐비트(입력 + 출력)에 하다마드 게이트를 적용합니다.
    for qubit in range(n_qubits + 1):
        dj_circuit.h(qubit)

    # 4. 오라클 회로를 추가합니다.
    dj_circuit.compose(oracle, inplace=True)

    # 5. 입력 큐비트에 다시 하다마드 게이트를 적용합니다(출력 큐비트는 제외).
    for qubit in range(n_qubits):
        dj_circuit.h(qubit)

    # 6. 마지막으로 입력 큐비트를 측정합니다.
    for qubit in range(n_qubits):
        dj_circuit.measure(qubit, qubit)

    return dj_circuit
```


### 4. 'constant' vs 'balanced' 테스트를 위한 통합 실행 코드

```python3
def run_deutsch_jozsa_test(n_qubits, oracle_type='constant', constant_output=0):
    """
    상수 오라클 또는 balanced 오라클에 대해 도이치–조자 회로를 구성하고 실행한 뒤 결과를 출력합니다.

    매개변수:
        n_qubits (int): 입력 큐비트의 수.
        oracle_type (str): 오라클 유형('constant' 또는 'balanced').
        constant_output (int): 오라클이 상수일 경우, 0 또는 1을 반환하도록 설정.

    """
    # 선택된 오라클 생성
    if oracle_type == 'constant':
        oracle = create_constant_oracle(n_qubits, constant_output)
        print(f"Using a CONSTANT oracle that always returns {constant_output}")
    else:
        oracle = create_balanced_oracle(n_qubits)
        print("Using a BALANCED oracle.")

    # 도이치–조사 회로 생성
    dj_circ = deutsch_jozsa_circuit(oracle, n_qubits)

    # 회로 시각화
    display(dj_circ.draw())

    # 시뮬레이터 백엔드를 사용하여 회로 실행
    simulator = Aer.get_backend('aer_simulator')
    transpiled_circ = transpile(dj_circ, simulator)
    job = simulator.run(transpiled_circ, shots=1)
    result = job.result()
    counts = result.get_counts(transpiled_circ)

    print("Measurement outcomes:", counts)

    # 측정 결과 해석
    # 모든 측정 비트가 0(예: 3큐비트면 '000')이면 함수는 'constant'입니다.
    # 그렇지 않으면 'balanced'입니다.
    measured_result = max(counts, key=counts.get)
    if measured_result == '0' * n_qubits:
        print("Conclusion: f(x) is CONSTANT.")
    else:
        print("Conclusion: f(x) is BALANCED.")
```


### 5. 예시 실행

```python3
# 3개의 큐비트로 테스트
run_deutsch_jozsa_test(n_qubits=3, oracle_type='constant', constant_output=0)

print("\n" + "="*50 + "\n")

run_deutsch_jozsa_test(n_qubits=3, oracle_type='balanced')
```


### 실행 결과:

```
Using a CONSTANT oracle that always returns 0
     ┌───┐┌───┐┌─┐      
q_0: ┤ H ├┤ H ├┤M├──────
     ├───┤├───┤└╥┘┌─┐   
q_1: ┤ H ├┤ H ├─╫─┤M├───
     ├───┤├───┤ ║ └╥┘┌─┐
q_2: ┤ H ├┤ H ├─╫──╫─┤M├
     ├───┤├───┤ ║  ║ └╥┘
q_3: ┤ X ├┤ H ├─╫──╫──╫─
     └───┘└───┘ ║  ║  ║ 
c: 3/═══════════╩══╩══╩═
                0  1  2 
Measurement outcomes: {'000': 1}
Conclusion: f(x) is CONSTANT.

==================================================

Using a BALANCED oracle.
     ┌───┐          ┌───┐   ┌─┐
q_0: ┤ H ├───────■──┤ H ├───┤M├
     ├───┤┌───┐  │  └┬─┬┘   └╥┘
q_1: ┤ H ├┤ H ├──┼───┤M├─────╫─
     ├───┤├───┤  │   └╥┘ ┌─┐ ║ 
q_2: ┤ H ├┤ H ├──┼────╫──┤M├─╫─
     ├───┤├───┤┌─┴─┐  ║  └╥┘ ║ 
q_3: ┤ X ├┤ H ├┤ X ├──╫───╫──╫─
     └───┘└───┘└───┘  ║   ║  ║ 
c: 3/═════════════════╩═══╩══╩═
                      1   2  0 
Measurement outcomes: {'001': 1}
Conclusion: f(x) is BALANCED.
```


### 코드 설명

#### 1. 라이브러리 불러들이기
* `QuantumCircuit`를 사용하여 양자 회로를 만듭니다.
* `Aer`, `transpile`, `run`을 사용하여 고전 시뮬레이터에서 회로를 실행합니다.

#### 2. 오라클 생성
* **상수(Constant) 오라클**: 모든 입력에 대해 같은 값을 반환합니다(0 또는 1). 코드에서는 오라클이 1을 항상 반환하도록 해야 할 경우 출력 큐비트를 뒤집습니다.
* **Balanced 오라클**: 절반의 입력에는 0을, 절반의 입력에는 1을 반환합니다. 예시에서는 첫 번째 입력 큐비트가 1일 때 출력 큐비트를 뒤집는 `CNOT` 게이트(`cx`)를 사용합니다.

#### 3. 도이치–조사 회로 구성
# 모든 입력 큐비트를 \vert 0 \rangle 상태로 시작하고, 출력 큐비트를 X 게이트로 \vert 1 \rangle 상태로 만듭니다.
# 하다마드 게이트(`dj_circuit.h(qubit)`)를 입력 및 출력 큐비트에 적용하여 \vert 0 \rangle와 \vert 1 \rangle 상태가 균등하게 퍼지도록 만듭니다(중첩 상태).
# 오라클을 연결하여 함수 f(x)에 따라 출력 큐비트를 수정합니다.
# 입력 큐비트에 다시 하다마드 게이트를 적용하여 (f)가 상수인지 balanced인지 나타나는 간섭 패턴을 생성합니다.
# 마지막으로 모든 입력 큐비트를 측정합니다.

#### 4. 결과 해석
# (f)가 **상수**라면, 100% 확률로 \vert 0 ... 0 \rangle (즉 모든 측정 결과가 0) 상태가 나타납니다.
# (f)가 **balanced**라면, 측정 결과가 전부 0이 아닌 다른 패턴이 나타납니다.

#### 5. 알고리즘 실행
우리는 Aer의 `aer_simulator`를 사용해 회로를 실행합니다. 도이치–조자 알고리즘은 상수와 balanced를 구분하기 위해 한 번의 오라클 호출만 필요하기 때문에, 여러 번의 샷(shots)을 실행해도 결과는 동일하게 나옵니다.

### 고전적 결정론적 컴퓨터보다 빠른 이유
고전적으로는 (f)(“미스터리”한 블랙박스 함수)가 constant인지 balanced인지 확실히 판별하기 위해 최대 2^{n-1} + 1번의 함수 호출이 필요할 수 있습니다. 하지만 양자 버전은 오라클 한 번의 호출과 몇 개의 추가 양자 게이트만으로 문제를 해결할 수 있습니다. 도이치–조사 알고리즘은 실용적인 응용 예시보다는 교육용 예시로 더 많이 거론되지만, 중첩(superposition)과 간섭(interference)을 활용해 함수 호출 횟수를 급격히 줄이는 양자 알고리즘의 핵심 아이디어를 잘 보여줍니다.

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

## 각주

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

분류:양자 알고리즘