6. Introductory Quantum Algorithms

양자 알고리즘은 고전 확률 알고리즘과 일부 특징을 공유합니다.

그렇기 때문에 먼저 두가지 알고리즘의 비교부터 시작하겠습니다

Classical Probability

고전확률모형의 경우, State 와 State Transition에 대한 Probability로 Tree 모형을 만들 수 있습니다.

확률트리에서 최종적인 node에 도달할 확률은, root로부터 leaf 까지의 확률의 곱으로 나타납니다.

이 때, Transition 하는 확률 Probability $p_{0,0}$ 가 있고, 이 확률은 probability Amplitude의 squared norm 입니다 $p_{0,j}=|\alpha_{0,j}|^2$

이러한 Probability Amplitude의 개념이 Quantum Algorithm 에도 그대로 적용이 됩니다.

그런데 다른 점은, 이 확률은 state가 변했을 때 즉시 결정되지 않습니다. Quantum Probability Amplitude 에서는 Interfere(간섭) 이 생길 수 있습니다. 따라서 (-) 음의 부호를 가지는 Amplitude가 (+) 부호의 Amplitude과 간섭이 일어나 Cancellation 이 발생할 수 있습니다.

개념의 발전 : $prob = \Sigma p_{0,j}q_{j,3}$ → $prob = \Sigma |\alpha_{0,j}\beta_{j,3}|^2$ → $prob = |\Sigma \alpha_{0,j}\beta_{j,3}|^2$

이렇게 보면 고전 확률과 양자 확률에서 크게 다르지 않은 것 같아 보입니다. 하지만 Control Input 또한 Entangled 라면 어떻게 될까요? 아래에서 같이 알아봅시다.

Quantum Parallelism ( Oracle , Phase Kick-back )

4장에서 우린 Reversible 의 정의를 보았습니다. 기억나지 않을 수도 있으니 다시 한번 봅시다

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad Reversible_f : |x\rangle|y\rangle → |x\rangle|y ⊕ f(x) \rangle$

이 정의를 이용하여 , CNOT Gate를 다시 표현해보겠습니다

$\quad\quad\quad\quad\quad\quad\quad CNOT : |x\rangle({|0\rangle - |1\rangle \over \sqrt2}) → |x\rangle({|0⊕ f(x)\rangle - |1⊕ f(x)\rangle \over \sqrt2}) = (-1)^{f(x)}|x\rangle({|0\rangle - |1\rangle \over \sqrt2})$

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad f : f(x) \; is \; NOT \; gate$

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad where, NOT(X) \; Gate's \; Eigenvector = {|0\rangle - |1\rangle \over \sqrt2}$

여기에 Control Input 이 superposition 되어있다면 어떻게 표현될까요?

$\quad\quad CNOT : (\alpha_0|0\rangle+\alpha_1|1\rangle)({|0\rangle - |1\rangle \over \sqrt2}) → ((-1)^{f(0)}\alpha_0|0\rangle + (-1)^{f(1)}\alpha_1|1\rangle)|x\rangle({|0\rangle - |1\rangle \over \sqrt2})$

⇒ Hadamard Gate를 n개 사용하면 $2^n$ 의 중첩된 상태를 동시에 만들어 낼 수 있습니다.

자 이제 이 CNOT Gate를 확장시켜서 Unitary 의 개념에서 봅시다

$U_f ==c-U_f : |x\rangle({|0\rangle - |1\rangle \over \sqrt2}) → (-1)^{f(x)}|x\rangle({|0\rangle - |1\rangle \over \sqrt2})$

Phase Kickback

A university quantum algorithms/computation course supplement based on Qiskit

https://qiskit.org/textbook/ch-gates/phase-kickback.html

Deutsch Algorithm

1985년 Dvid Deutsch 가 발표한 최초의 양자 알고리즘 입니다.

Quantun Parallelism 과 Interference 를 활용한 알고리즘 입니다.

(가정) Reversible 한 Black-box ( or Oracle) 을 정의합니다.

그리고 Input을 던지고 Output 을 통해서 이 Black-box를 추정합니다 $if f(0)⊕f(1)=0 , \quad then \; f(0)=f(1)$ → function is "constant" $if f(0)⊕f(1)=1 , \quad then \; f(0)≠f(1)$ → function is "balanced"

Classical Computing 에서는 2번 연산 해야 할 것을, Quantum Computing 에서는 Hadamard Gate를 통과시킴으로써 1번 (Single Query)만 연산 하면 된다는 점에 의의가 있습니다.

Constant Oracle
- 오라클이 일정하면 입력에 영향을 주지 않으며 오라클을 쿼리하기 전과 후의 퀀텀 상태는 동일합니다. 첫번째 레지스터에서 초기 양자 상태를 얻을 수 있습니다.

Balanced Oracle
- 오라클이 균형을 이루면, pahse kickback은 정확히 절반에 negative를 추가합니다.
- 오라클을 쿼리 한 후의 상태는 쿼리 전의 퀀텀과 Orthogonal 합니다

Deutsch-Jozsa Algorithm

Deutsch Algorithm 의 일반화된 경우입니다.

1992년에 David Deustch , Richard Jozsa 가 발표했습니다.

Classical Computer 를 사용할 경우 $2^{n-1}+1$ 번 연산해야합니다. 운이 나쁘면 x 중 최소 절반 이상을 확인해야 첫번째와 두번쨰 경우를 100% 구분할 수 있기 때문입니다.

반면, Quantum Computer 는 단 한번 만 사용해도 100% 확률로 알아 낼 수 있습니다.

H^{⊗n}|0\rangle^{⊗n}={1 \over \sqrt{2^n}} \Sigma_{x∈{0,1}^n}|x\rangle

$|\psi\rangle \quad Amplitude \quad {1 \over 2^n} \Sigma (-1)^{f(x)}$

$x*z = \langle x|z\rangle \; mod \; 2$

Deutsch-Jozsa Algorithm

We are given a hidden Boolean function $f$, which takes as input a string of bits, and returns either $0$ or $1$, that is: $$ f(\{x_0,x_1,x_2,...\}) \rightarrow 0 \textrm{ or } 1 \textrm{ , where } x_n \textrm{ is } 0 \textrm{ or } 1$$ The property of the given Boolean function is that it is guaranteed to either be balanced or constant.

https://qiskit.org/textbook/ch-algorithms/deutsch-jozsa.html

Qiskit Code

# initialization
import numpy as np

# importing Qiskit
from qiskit import IBMQ, BasicAer
from qiskit.providers.ibmq import least_busy
from qiskit import QuantumCircuit, execute

# import basic plot tools
from qiskit.visualization import plot_histogram



# -- Create Oracle --#

def dj_oracle(case, n):
    # We need to make a QuantumCircuit object to return
    # This circuit has n+1 qubits: the size of the input,
    # plus one output qubit
    oracle_qc = QuantumCircuit(n+1)
    
    # First, let's deal with the case in which oracle is balanced
    if case == "balanced":
        # First generate a random number that tells us which CNOTs to
        # wrap in X-gates:
        b = np.random.randint(1,2**n)
        # Next, format 'b' as a binary string of length 'n', padded with zeros:
        b_str = format(b, '0'+str(n)+'b')
        # Next, we place the first X-gates. Each digit in our binary string 
        # corresponds to a qubit, if the digit is 0, we do nothing, if it's 1
        # we apply an X-gate to that qubit:
        for qubit in range(len(b_str)):
            if b_str[qubit] == '1':
                oracle_qc.x(qubit)
        # Do the controlled-NOT gates for each qubit, using the output qubit 
        # as the target:
        for qubit in range(n):
            oracle_qc.cx(qubit, n)
        # Next, place the final X-gates
        for qubit in range(len(b_str)):
            if b_str[qubit] == '1':
                oracle_qc.x(qubit)

    # Case in which oracle is constant
    if case == "constant":
        # First decide what the fixed output of the oracle will be
        # (either always 0 or always 1)
        output = np.random.randint(2)
        if output == 1:
            oracle_qc.x(n)
    
    oracle_gate = oracle_qc.to_gate()
    oracle_gate.name = "Oracle" # To show when we display the circuit
    return oracle_gate




# -- Alorithm -- #

def dj_algorithm(oracle, n):
    dj_circuit = QuantumCircuit(n+1, n)
    # Set up the output qubit:
    dj_circuit.x(n)
    dj_circuit.h(n)
    # And set up the input register:
    for qubit in range(n):
        dj_circuit.h(qubit)
    # Let's append the oracle gate to our circuit:
    dj_circuit.append(oracle, range(n+1))
    # Finally, perform the H-gates again and measure:
    for qubit in range(n):
        dj_circuit.h(qubit)
    
    for i in range(n):
        dj_circuit.measure(i, i)
    
    return dj_circuit



# -- Main function -- #

n = 4
oracle_gate = dj_oracle('balanced', n)
dj_circuit = dj_algorithm(oracle_gate, n)
dj_circuit.draw()



# -- Result -- #
results = execute(dj_circuit, backend=backend, shots=1024).result()
answer = results.get_counts()
plot_histogram(answer)

Simon's Algorithm

1994년 Daniel Simon이 고안한 알고리즘 입니다.

QFT에 영감을 주었으며 Shor 알고리즘의 핵심입니다.

[Problem] one-to-one, two-to-one 을 보장하는 Black-box function $f$ 가 있다. two-to-one 일 때는 다음을 보장한다. $f(x_1)=f(x_2) , \; x_1⊕b=x_2$ , b is hidden string $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad U_f : |x\rangle|b\rangle → |x\rangle|b⊕ f(x)\rangle$ Problem 1. → one-to-one / two-to-one 인지 찾는다 Problem 2. → two-to-one 일 때, 그러한 hidden string을 어떻게하면 빨리 찾을 수 있을까? Note. classical computing 에서는 $2^{n-1}+1$ 번 연산했다

💡

|\phi_0\rangle=|0,0\rangle

|\phi_1\rangle=(H^{⊗n}⊗I)|\phi_0\rangle={1 \over \sqrt{2^n}} \Sigma |x,0\rangle

|\phi_2\rangle=U_f|\phi_1\rangle = {1 \over \sqrt{2^n}} \Sigma |x,f(x)\rangle

|\phi_3\rangle=(H^{⊗n}⊗I)|\phi_2\rangle={1 \over {2^n}} \Sigma \Sigma(-1)^{<z|x>} |z,f(x)\rangle

📢

우리가 찾는 것은 $x_1⊕b=x_2$ 이고

(-1)^{<z|x>} |z,f(x)\rangle

에 x1, x2 를 넣어서

|\phi_3\rangle

을 다시 표현하면 아래와 같다

|\phi_3\rangle={1 \over {2^n}} \Sigma \Sigma {(-1)^{<z|x>}(1+(-1)^{<z|b>} \over 2}|z,f(x)\rangle

$⟨f(x),f(y)⟩= \begin {Bmatrix} 1 \quad when \; x=y\\ 0 \quad when \; x≠y\\ \end {Bmatrix}$ 이므로, $⟨f(x),f(y)⟩= \begin {Bmatrix} 1 \quad when \; x=y \; or \; x=y⊕b\\ 0 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad else \end {Bmatrix}$

|\Sigma {(-1)^{<z|x>}(1+(-1)^{<z|b>} \over 2}|f(x)\rangle|^2= \begin {Bmatrix} 2^n \quad when <z,b>=0\\ 0 \quad when <z,b>=0\\ \end {Bmatrix}

이후부터는 linear equation으로 풀면 된다. 왜 ? S⊥ 자체를 $\langle s | z \rangle =0$ 으로 하는 Subspace로 정의했기 때문 인용. So Simon's algorithm succeeds with probability of at least 1/4

⇒ So, the number of queris to function f used by Simon's Alogorithm is O(n)

Bernstein-Vazirani Algorithm

Bernstein-Vazirani Algorithm The Bernstein-Vazirani algorithm, first introduced in Reference [1], can be seen as an extension of the Deutsch-Josza algorithm we covered in the last section. It showed that there can be advantages in using a quantum computer as a computational tool for more complex problems than the Deutsch-Josza problem.

https://qiskit.org/textbook/ch-algorithms/bernstein-vazirani.html

$U_f : |x\rangle|b\rangle → |x\rangle|b⊕xa)\rangle$ 인 a 를 찾는 문제 (string)

Uploaded by Notion2Tistory v1.0.0

8. Algorithms Based on Amplitude Amplification (0)	2021.01.10
7. Algorithms with Superpolynomial Speed-up (0)	2021.01.10
5. Superdense Coding & Quantum Teleportation (0)	2021.01.10
4. A Quantum Model of Computation (0)	2021.01.10
3. Qubits & Framework of Quantum Mechanics (0)	2021.01.10

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

어쩌다개발

Neighbors

어쩌다개발

태그

최근글

댓글

공지사항

아카이브

Classical Probability

Quantum Parallelism ( Oracle , Phase Kick-back )

Deutsch Algorithm

Deutsch-Jozsa Algorithm

Simon's Algorithm

Bernstein-Vazirani Algorithm

'IBM C:LOUDERs > Quantum Computing' 카테고리의 다른 글

관련글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역