如何理解計算複雜度版本的「熱力學第二定律」？

01-12

出處：The Second Law of Quantum Complexity
作者：Adam R. Brown and Leonard Susskind
摘要：We give arguments for the existence of a thermodynamics of quantum complexity that includes a 「Second Law of Complexity」. To guide us, we derive a correspondence between the computational (circuit) complexity of a quantum system of K qubits,and the positional entropy of a related classical system with 2K degrees of freedom.We also argue that the kinetic entropy of the classical system is equivalent to the Kolmogorov complexity of the quantum Hamiltonian. We observe that the expected pattern of growth of the complexity of the quantum system parallels the growth of entropy of the classical system. We argue that the property of having less-than maximal complexity (uncomplexity) is a resource that can be expended to perform directed quantum computation.

Although this paper is not primarily about black holes, we find a surprising
interpretation of the uncomplexity-resource as the accessible volume of spacetime behind a black hole horizon.

最近關注了Susskind大佬的這個文章，不自量力來答一下。

計算複雜度在物理中的重要性在最近幾年才剛剛被注意到，2013年 Harlow／Hayden在文章1301.4504中，藉助複雜度作為工具來分析AMPS關於黑洞視界處的不光滑性（也就是火牆佯謬）的思想實驗。可以說是複雜度被弦論方面的研究者重視的開端。14年之後，在全息對偶的角度，複雜度才作為一個物理量被廣泛的研究。

首先說一下複雜度的意義：在量子電路中，給你一些基本操作（量子門），給一個初態，一個態的複雜度表示從這個初態構建到這個我們要的態所需要的最小的量子門的數目。

雖然在全息中有一些研究，不過都是通過在引力理論中來去計算它。在物理上，從量子電路的定義直接推廣得到的定義依然很模糊。因此如何給複雜度一個合理的定義是一個待解決的問題。Susskind這個文章主要的思路是這樣的，複雜度隨時間的演化經過猜測現在有了一個大致的曲線，同時根據黑洞混沌的研究，也基本可以斷定，降低複雜度的過程是不穩定的，也就是說對於一個幺正演化U， $U U^{dagger}$ 它是恆等算符，複雜度為0，但是經過在U和它的逆演化中間只要插入一個微擾，那麼複雜度經過很短的時間的減小之後又回重新增加。

基於這些性質，對於一個由K個量子比特組成的系統，它的希爾伯特空間的維數是 $2^{K}$ , 所以幺正演化U可以認為就是 $SU(2^{K})$ 這個李群中的一個元素，複雜度可以認為是從恆等元連接到這個元素U的測地線的長度。這是Nielson在2006年的文章中的思想。為了描述複雜度的性質，我們可以通過給這個李群添加一些結構來達到目的。

這篇文章更深入了一步，提出了描述複雜度的一個模型，既然測地線可以描述複雜度，而測地線可以認為是一個粒子走的最短的軌跡。而在經典力學中，我們都知道粒子走的線長可以定義為作用量，變分得到測地線方程。所以這裡就存在了兩個系統，真實的K個量子比特組成的量子系統，還有一個虛擬的有 $2^{K}$ 個自由度的經典系統。

以上，聯繫了一個量子系統和一個經典系統，而通過之前的分析，我們知道這個經典系統是構造出來描述量子體系的複雜度的。而複雜度的演化曲線是這樣的：

它增長達到最大值的時間 $t sim e^{K}$ , 而達到熱平衡的過程中，熵增長的時間則是正比於K。那麼自然有一個想法，如果體系是 $e^{K}$ 個自由度，那麼它的熵增長曲線正好就是這樣的了。

而構造出的虛擬的經典體系，正好就是這麼多的自由度。所以，我們可以通過研究這個經典體系的熱力學性質，得到量子體系的複雜度的信息。這就是這篇文章的大致思想。

$C_{Q}=S_{A}$ .

也就是說這篇文章，將一個體系的複雜度和另一個體系的熵建立起來了聯繫，那麼熵所滿足的熱力學定律自然也就適用於複雜度，這也就是題目中問的「複雜度版本的熱力學第二定律」。同時，因為在混沌系統中，降低熵具有不穩定性，所以複雜度的第二定律的意思也可以理解成降低複雜度的操作都是不穩定的。

這個文章另外一個有意思的量是Uncomplexity，也是從這個對應來的。在熱力學中，很多能量必須以熱能的形式被浪費，能夠用來做功的量是F＝U-TS. 而這裡的對應意味著，F=U-TC. 文中證明在K確定時，U和T都是固定的。那麼現有的複雜度和可能的最大的複雜度之間的差值 $Delta C=C_{max}-C$ ，就可以作為能夠做功的保證。在量子體系方面，也就意味著這個差值可以作為進行有效計算能利用的資源。黑洞雖然是一台最快的計算機，但這個最快也是最無用的，能否有目的的被利用取決於這個叫做Uncomplexity的量。

作為提問者，我在等待靠譜回答的時間裡自己也做了些調查，不過還沒有比較滿意的收穫，已確定的部分分享在這裡：

1，從原文中能明確看出的是線路複雜度對應於作用量。由同類文獻啟發得出一個更直觀的理解：作用量對應於相位，相位近似正比於必需的量子門數。

@安宇森的答案所提及的測地線長度是作用量在物理中的另外一種表現形式。

（作用量即計算量的思想至少可以追溯到Norman H.Margolus and Lev B. Levitin. The maximum speed of dynamical evolution.Physica D, 120:188–195, 1998. quant-ph/9710043）

2，如果原文中的增長曲線是準確的，那麼或可用實驗測量的方法來確定給定函數的線路複雜度。

要知道，任意地有效求解線路複雜度意味著可以有效攻破因數分解和離散對數問題，對現行的信息安全體制構成重大威脅——量子計算受到的重視一定程度上就是來自相同的原因。但是線路複雜度有效解法的影響力更強一些，它甚至有助於對付所有的單向函數。

不過，這必須建立在結果能夠被推廣到任意演化過程的前提下，但原文的論證太過模糊，我不能肯定這種做法有充分的依據。