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)

Simon's Algorithm

Hello Underworld.

https://leimao.github.io/blog/Simon-Algorithm/

Simon's Algorithm

Simon's algorithm, first introduced in Reference [1], was the first quantum algorithm to show an exponential speed-up versus the best classical algorithm in solving a specific problem. This inspired the quantum algorithms based on the quantum Fourier transform, which is used in the most famous quantum algorithm: Shor's factoring algorithm.

https://qiskit.org/textbook/ch-algorithms/simon.html#2.-Example--

Bernstein-Vazirani Algorithm

---

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