量子随機遊走系列(一)

量子随機遊走

New綜述閱讀(一)

J Kempe (2003) Quantum random walks: An introductory overview, Contemporary Physics, 44:4, 307-327, DOI: 10.1080/00107151031000110776

Abstract

   文章緻力于提供一份量子随機遊走研究的介紹型綜述。全文從實體效應出發解釋了我們在量子随機遊走當中會介紹的主要觀點，回顧了它們的特性，并與傳統随機遊走的特性進行差異比較。随後從實體效應以及計算機科學應用領域，介紹一些量子随機遊走的概念和主要術語。最後，提及部分在這一新領域當中的進展，并給出一些開放性問題。

1. Overview

    自量子理論發現開始，人們就對自然法制違背直覺的特性感到困惑。随着時間推移，我們學會接受越來越多在牛頓理論世界中無法想象的效應。現代技術利用量子效應對我們有利有弊，人們應當在看到雷射技術的同時又不忽略原子彈。

   最近，對量子資訊理論的興趣日益高漲，人們期待利用量子法則設計擁有驚人能量的裝置。新觀點包括量子密碼學[2][3]和量子計算[4]。1994年Shor[4]發現了一種有效分解數字的量子算法(這一時期，多項式僅随要分解的數的長度而增長)。這在實體，計算機科學，數學和工程學等廣泛學科領域掀起了一股熱潮。

   這個研究方向已經發現了許多新的效果，無論是從實體角度還是從計算機科學和通信理論的角度來看，它們都與經典的效果截然不同。随着時間的流逝，這些社群對其他群體的概念和表示有了更深入的了解。資訊無法與承載它的實體裝置分離的想法（資訊即實體）已經牢牢地紮根于其中，并引發了令人着迷的新見解。熟悉這些領域的基本概念似乎有助于了解現代量子資訊處理。

   在本文中，我們将遵循量子資訊衆多令人驚訝的方面之一的軌迹：它緻力于量子随機遊走。我們将全面介紹必要的術語，而不會給讀者增加不必要的數學負擔。從一個非常直覺和實際的例子開始，我們将逐漸介紹當今量子資訊科學的語言和符号。我們将介紹實體學家了解和欣賞研究進展和結果所需要的計算機科學的必要背景，假設量子力學具有一些基本的背景知識，但不具備計算機科學或量子資訊論的知識。有關量子資訊和計算的出色綜合介紹，請參見[1]。

   在此過程中，我們将沿着幾門傳統學科的接口進行實體學和計算機科學領域的量子随機遊走。這次量子資訊科學之旅将使我們能夠研究當今一些最相關的概念和思想，例如量子算法，量子計算機，加速，實體實作，量子電路和退相幹。我們的任務是展示實體現象如何轉化為新的計算機科學算法，或者是對應的逆過程。假定讀者熟悉量子力學标準習語但不習慣“量子位”和“門”語言，我們将教授量子資訊科學，同時介紹量子随機遊走及其引人入勝的行為。我們将調查一些最新的進展和結果，并省略大多數證據，而是嘗試建立直覺感受。 本文旨在将感興趣的讀者帶到一個點，使其可以閱讀和了解有關該主題的最新研究文章，并對該領域的有趣問題和開放性問題有所了解。

   文章結構如下：首先，我們對随機行走給出一些實體直覺，進而在實體環境中大緻了解該現象(第2節)。接下來是更嚴格的定義以及一些必要的術語，以介紹第3節中的兩種主要的量子随機遊走模型。然後，我們介紹了一些計算機科學和機率背景，并在第4節中提到了一些來自量子随機遊走的重要算法結果。第5節轉回到實體學，研究如何在某些實際實體系統中實作這些随機遊走。最後，我們處理一個更哲學的問題，即經典世界如何通過以随機遊走為例的退相幹從量子行為中脫穎而出(第6節)。在整個過程中，我們将概述未解決的問題和未來的方向。

2. A gentle introduction

   為描述量子随機遊走并對其中發生的事情有一個直覺描述，我們從一個示例出發。這個例子(可能被認為是之後模型的先驅)是從1993年這項工作中[5]提取出來的。在他們的工作中，“量子随機行走”第一次被創造出來。

   想象線上的一個粒子，它的位置由位于位置 x o x_o xo​的波束 ∣ Ψ x o ⟩ \left |\Psi_{x_o} \right \rangle ∣Ψxo​​⟩決定， i . e . i.e. i.e.函數 ⟨ x ∣ Ψ x o ⟩ \left \langle x|\Psi_{x_o} \right \rangle ⟨x∣Ψxo​​⟩對應于處在 x o x_o xo​處的波束。令P為動量算子，粒子平移步長 l l l由一進制運算符 U l = e x p ( − i P l / h ) U_l=exp(-iPl/h) Ul​=exp(−iPl/h)表示，是以 U l ∣ ψ x o ⟩ = ∣ ψ x o − l ⟩ U_l|\psi_{x_o}\rangle=|\psi_{x_o-l}\rangle Ul​∣ψxo​​⟩=∣ψxo​−l​⟩。現在假設粒子有自旋 1 / 2 1/2 1/2自由度，以 S z S_z Sz​表示自旋的 z z z元件，以 ∣ ↑ ⟩ |\uparrow\rangle ∣↑⟩和 ∣ ↓ ⟩ |\downarrow\rangle ∣↓⟩表示 S z S_z Sz​的特征态，進而， S z ∣ ↑ ⟩ = ( h / 2 ) ∣ ↑ ⟩ S_z|\uparrow\rangle=(h/2)|\uparrow\rangle Sz​∣↑⟩=(h/2)∣↑⟩， S z ∣ ↓ ⟩ = − ( h / 2 ) ∣ ↓ ⟩ S_z|\downarrow\rangle=-(h/2)|\downarrow\rangle Sz​∣↓⟩=−(h/2)∣↓⟩。目前，設定 h = 1 h=1 h=1來簡化表達。

   一個自旋 1 / 2 1/2 1/2的粒子經常以 2 2 2位向量表示： ∣ ψ ⟩ = ( ∣ ψ ~ ↑ ⟩ , ∣ ψ ~ ↓ ⟩ ) T |\psi\rangle=(|\widetilde{\psi}^{\uparrow}\rangle,|\widetilde{\psi}^{\downarrow}\rangle)^T ∣ψ⟩=(∣ψ

​↑⟩,∣ψ

​↓⟩)T，第一部分是自旋空間 ∣ ↑ ⟩ |\uparrow\rangle ∣↑⟩上粒子的波函數元件，第二部分是 ∣ ↓ ⟩ |\downarrow\rangle ∣↓⟩上粒子的波函數元件。正則化需要滿足： ∣ ∥ ψ ~ ↑ ⟩ ∥ 2 + ∥ ψ ~ ↓ ⟩ ∥ 2 ∣ = 1 |\left \| \widetilde{\psi}^{\uparrow}\rangle \right \|^2 + \left \| \widetilde{\psi}^{\downarrow}\rangle \right \|^2|=1 ∣∥∥∥​ψ

​↑⟩∥∥∥​2+∥∥∥​ψ

​↓⟩∥∥∥​2∣=1。為強調粒子空間的張量結構，我們将以一種略有不同的方式表示它： ∣ ψ ⟩ = α ↑ ∣ ↑ ⟩ ⨂ ∣ ψ ↑ ⟩ + α ↓ ∣ ↓ ⟩ ⨂ ∣ ψ ↓ ⟩ |\psi\rangle=\alpha^{\uparrow}|\uparrow\rangle\bigotimes|\psi^{\uparrow}\rangle+\alpha^{\downarrow}|\downarrow\rangle\bigotimes|\psi^{\downarrow}\rangle ∣ψ⟩=α↑∣↑⟩⨂∣ψ↑⟩+α↓∣↓⟩⨂∣ψ↓⟩，此處将兩個波函數正則化為 ⟨ ψ ~ ↑ ∣ ψ ~ ↑ ⟩ = ⟨ ψ ~ ↓ ∣ ψ ~ ↓ ⟩ = 1 \langle\widetilde{\psi}^{\uparrow} |\widetilde{\psi}^{\uparrow}\rangle=\langle\widetilde{\psi}^{\downarrow} |\widetilde{\psi}^{\downarrow}\rangle=1 ⟨ψ

​↑∣ψ

​↑⟩=⟨ψ

​↓∣ψ

​↓⟩=1，進而 ∣ α ↑ ∣ 2 + ∣ α ↓ ∣ 2 = 1 |\alpha^{\uparrow}|^2+|\alpha^{\downarrow}|^2=1 ∣α↑∣2+∣α↓∣2=1。張量積 ′ ⨂ ′ '\bigotimes' ′⨂′将将兩個自由度（自旋和空間）分開，這将使我們能夠更清晰地檢視這兩個自由度之間的相關性。現在，對應于更大 1 / 2 1/2 1/2自旋粒子狀态空間的平移 l l l的時間發展能借助算子描述： U = e x p ( − 2 i S z ⨂ P l ) U=exp(-2iS_z \bigotimes Pl) U=exp(−2iSz​⨂Pl)。算子依據自旋粒子的内部自旋自由度來産生條件平移。特别地，若粒子的自旋初始化為狀态 ∣ ↑ ⟩ |\uparrow \rangle ∣↑⟩，對應的波函數為 ∣ ↑ ⟩ ⨂ ∣ ψ x o ↑ ⟩ |\uparrow \rangle \bigotimes | \psi_{x_o}^{\uparrow} \rangle ∣↑⟩⨂∣ψxo​↑​⟩，對 ∣ ↑ ⟩ ⨂ ∣ ψ x o − 1 ↑ ⟩ |\uparrow \rangle \bigotimes | \psi_{x_o-1}^{\uparrow} \rangle ∣↑⟩⨂∣ψxo​−1↑​⟩應用 U U U平移，如此粒子會向右偏移 l l l。如果粒子自旋态是 ∣ ↓ ⟩ |\downarrow \rangle ∣↓⟩， i . e . i.e. i.e.整個波函數用 ∣ ↓ ⟩ ⨂ ∣ ψ x o ↓ ⟩ |\downarrow \rangle \bigotimes | \psi_{x_o}^{\downarrow} \rangle ∣↓⟩⨂∣ψxo​↓​⟩給定，接着平移算子會将其轉換為 ∣ ↓ ⟩ ⨂ ∣ ψ x o + 1 ↓ ⟩ |\downarrow \rangle \bigotimes | \psi_{x_o+1}^{\downarrow} \rangle ∣↓⟩⨂∣ψxo​+1↓​⟩，粒子會向左偏移。更有趣的行為會出現在以下的情況中，當粒子初始自旋狀态，定位于 x o x_o xo​，不是 S z S_z Sz​的特征态，而是位于一個疊加态：

∣ ψ i n ⟩ = ( α ↑ ∣ ↑ ⟩ + α ↓ ∣ ↓ ⟩ ) ⨂ ∣ ψ x o ⟩ | \psi_{in} \rangle = (\alpha^{\uparrow} | \uparrow \rangle + \alpha^{\downarrow} | \downarrow \rangle) \bigotimes | \psi_{x_o} \rangle ∣ψin​⟩=(α↑∣↑⟩+α↓∣↓⟩)⨂∣ψxo​​⟩

應用平移算子 U U U産生位置的疊加态

U ∣ ψ i n ⟩ = α ↑ ∣ ↑ ⟩ ⨂ ∣ ψ x o − l ⟩ + α ↓ ∣ ↓ ⟩ ⨂ ∣ ψ x o + l ⟩ U | \psi_{in} \rangle = \alpha^{\uparrow} | \uparrow \rangle \bigotimes | \psi_{x_o-l} \rangle + \alpha^{\downarrow} | \downarrow \rangle \bigotimes | \psi_{x_o+l} \rangle U∣ψin​⟩=α↑∣↑⟩⨂∣ψxo​−l​⟩+α↓∣↓⟩⨂∣ψxo​+l​⟩

若在該點上我們決定在 S z S_z Sz​基礎上測量旋轉态，粒子要麼位于 x o − l x_o-l xo​−l以 p ↑ = ∣ α ↑ ∣ 2 p^{\uparrow}=|\alpha^{\uparrow}|^2 p↑=∣α↑∣2機率處在狀态$$

• [1] Nielsen, M. A., and Chuang, I. L., 2000, Quantum Computation and Quantum Information (Cambridge: Cambridge University Press).

• [2] Hughes, R. J., Alde, D. M., Dyer, P., Luther, G. G., Morgan, G. L., and Schauer, M., 1995, Contemp. Phys., 36, 149.

• [3] Gisin, N., Ribordy, G. G., Tittel, W., and Zbinden, H., 2002, Rev. Mod. Phys., 74, 145.

• [4] Shor, P. W., 1994, in Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, edited by S. Goldwasser (Los Alamitos, CA: IEEE Computer Society), pp. 124 – 134 (final version in [52]).