도이치–조사 알고리듬

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

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

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

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

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

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

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

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

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

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

  .

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

  .

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

 .

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



부분만 고려하면 된다

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



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



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



로 측정됨을 알 수 있다.

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



이다.

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

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

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



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





를 얻는다.

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



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




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

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

1. 필요한 라이브러리 불러들이기
from qiskit import QuantumCircuit, transpile
from qiskit_aer import Aer

2. 오라클을 생성하는 도움 함수 정의
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. 도이치–조사 회로를 조립하는 함수
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' 테스트를 위한 통합 실행 코드
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. 예시 실행
# 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. 도이치–조사 회로 구성
 모든 입력 큐비트를  상태로 시작하고, 출력 큐비트를 X 게이트로  상태로 만듭니다.
 하다마드 게이트(dj_circuit.h(qubit))를 입력 및 출력 큐비트에 적용하여 와  상태가 균등하게 퍼지도록 만듭니다(중첩 상태).
 오라클을 연결하여 함수 f(x)에 따라 출력 큐비트를 수정합니다.
 입력 큐비트에 다시 하다마드 게이트를 적용하여 (f)가 상수인지 balanced인지 나타나는 간섭 패턴을 생성합니다.
 마지막으로 모든 입력 큐비트를 측정합니다.

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

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

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

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

 각주 

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

분류:양자 알고리즘