Welcome

Finally got some time to play with my Raspberry Pi again! In my earlier post "LlamaPi: Experiments with VideoCore GPU", I tried to run llama.cpp on Raspberry Pi's VideoCore GPU through Vulkan. That experiment was not very successful: Although he program could run, the data it generated was garbage and the generation speed is even slower than CPU. Recently I looked into this experiment again and made some progress. I got llama.cpp to run with GPU offload on Raspberry Pi and generate correct data. Athough the generation speed with Raspberry Pi GPU was still slower than CPU, it demonstrated the technical feasibilty of GPU offloading on Raspberry Pi. Built the environment for cross compiling Vulkan program that runs on Raspberry Pi. Cross Compiling of RPi Vulkan program Motivation: Native compiling doesn't work The first challenge was compiling llama.cpp with Vulkan support for Raspberry Pi. ...

Introduction 我经常使用 Emacs Org-mode 来写blog。虽然有很多其他笔记工具和方案，但我一直觉得没法取代 Org-mode，比如Org-mode里的 Babel 代码块，内嵌LaTex公式，GUI下图表预览，表格自动求值等功能，实在是很方便。Emacs Org-mode 也天然支持将众多 org 文件笔记通过链接组织成个人知识库。 不过，现有的工作流基于标准的 ox-publish 导出 HTML，样式略显陈旧，如果支持更美观的主题，需要很多手动配置。 最近对orgmode工作进行了一次升级：引入 Hugo 渲染引擎（搭配 PaperMod 主题），同时保留了纯粹的 Org-mode 创作体验。 工作流的演进 过去：Org -> HTML (ox-publish) 优点：流程简单，完全受 Emacs 控制。 缺点：网页样式极其基本，移动端适配差，缺乏搜索和标签功能。 现在：Org -> HTML Fragment -> Hugo (PaperMod) 改进：采用 Hugo 作为渲染引擎，利用 PaperMod 提供现代化的 UI。 核心逻辑：利用 Emacs 的 ox-html 将 Org 导出为纯净的 HTML 片段，再交给 Hugo 进行最终装配。 关键技术点 1. 自动化导出脚本：publish-hugo.el 这是整个流程的“心脏”。它是一个 Emacs Lisp 脚本，通过 Org 内置的 ox-html 导出器实现精准渲染，同时负责元数据注入和路径修正。 (defun pz/export-all-to-hugo () (dolist (section '("notes" "quantum" "me")) (dolist (file (directory-files (expand-file-name section) t "\\.org$")) (with-current-buffer (find-file-noselect file) ;; 导出为 HTML 片段 (let ((html-content (org-export-as 'html nil nil t))) ;; 修复资源路径 (setq html-content (replace-regexp-in-string "\\.\\./images/" "/images/" html-content)) ;; 写入 Hugo content 目录 (with-temp-file dest-file (insert "---\n" (format "title: \"%s\"\n" title) "math: true\n---\n\n") (insert html-content))))))) 2. 构建与部署：build.sh & deploy.sh 实现“一键发布”的两个 Bash 脚本： ...

最近RWKV有不少进展，RWKV-7出了思考模型 rwkv-7-world-g1 ，RWKV-8也即将发布。 RWKV的模型架构，在计算量和内存上相比Transformer有很大的优势，对于LlamaPi这种在边缘设备上运行的应用很有吸引力。因此尝试在LlamaPi上适配RWKV，看看效果如何。 目前初步尝试，总的来说不太成功，可能是使用方法或适配上还有些问题，模型始终不能很好的遵循系统指令，生成符合要求的响应。 llama.cpp运行 按照文档步骤： 编译最新的llama.cpp 下载 rwkv7-g1-1.5b-20250429-ctx4096 ，转换成gguf，Q80量化 用 llama-cli 命令行运行，提示词参考LlamaPi： ./build/bin/llama-cli -m models/rwkv7-g1-1.5b-20250429-ctx4096-Q8_0.gguf -p "Your name is Skyler. You are a helpful assistant.\n\n" -cnv -t 4 -ngl 99 -n 500 启动后本来应该就进入对话的，但它先进入了自嗨模式，输出了一大通不相关的东西，然后才停下进入提示符。这可能还是因为我设了n=500的参数，否则不知道它什么时候会停下： 然后检查一下提示词的有效性，结果是完全没用： > hello, what's your name? My name is [My name] > who are you? My name is [My name] > 命令行不行，那试试Web界面？ /build/bin/llama-server -m models/rwkv7-g1-1.5b-20250429-ctx4096-Q8_0.gguf 先设置一下系统提示： 试一下，这次系统提示词似乎有效了。 试试LlamaPi的完整提示词： ...

As mentioned in my previous posts, I've been trying to get LlamaPi to run with VideoCore GPU on Raspberry Pi, hoping to further boost generation speed. Well, that effort might have just come to a conclusion… TL;DR is that VideoCore on Raspberry Pi is not well suited for such computation - in fact, it is even much slower than the ARM CPUs on Raspberry Pi. In case I need them again, here are some of the records of my experiments. ...

LlamaPi now supports Gemini as its backing LLM, in addition to local LLM and Coze. On Gemini side: Test the prompt (system instruction) for using with LlamaPi. Create an API key (may need to create a project first). On LlamaPi side: Create a wrapper using Gemini Python SDK. In order to support multiple backing LLMs, major refactor was done to the LlamaPi code. Create a common base class LlamaPiBase for all three scenarios (local, Coze, Gemini). The base class includes the common functionalities like the UI, audio, ASR, etc. Created subclasses for local LLM, Coze and Gemini respectively. They extend the base class and implement the logic for interacting with backing LLMs. With this refactor, it will be easier for me to add support for other LLMs in the furture. ...

I just updated LlamaPi with Llama-3.2 3B as its default local LLM. Similar to Llama-3.1, I need to convert the model into gguf format, and then quantize it into different sizes. For 5-bit quantization, memory usage was reduced to ~2.7GB and generation speed reached 3.3 tokens/second. Compared to Llama-3.1 8B (4-bit quantized), the speedup is 1.83x. Here is a comparison using llama.cpp CLI:   tokens/second Llama-3.1 8B (4-bit quantized) 1.8 Llama-3.2 3B (8-bit quantized) 2.5 Llama-3.2 3B (5-bit quantized) 3.3 Generation quality seemed to be similar as Llama-3.1 8B, but I haven't had time to compare them extensively yet. ...

Intro Recently I built a prototype demonstrating the possibilities of Voice + LLM + Robotics. It is a voice chatbot running on Raspberry Pi 5 backed by the latest LLM (e.g. Llama-3.1), allowing the user to control robot arm gestures through voice interactions. Backed by local LLM (Llama-3.1 8B) or cloud-based LLM. Local ASR (faster_whisper) and TTS (piper). Robot arm commands generated by LLM based on the context of the conversation. The prototype won 1st and 3nd prizes at the recent InfiniEdge AI Hackathon. ...

这是一篇北大和UCSD合作的论文，主题是优化大模型推理服务的性能。 在前文（RWKV）中提到过，对于大语言模型（LLM）来说，更大的挑战是推理。因为推理成本属于OpEx，用户使用越多，花费就越大。降低LLM的推理服务成本，是LLM应用在商业上可持续的关键之一。 LLM推理服务对性能的要求，也与训练有所不同。推理服务更注重响应的延迟，由于直接面向用户，响应延迟直接影响用户体验。例如对于聊天机器人类型的应用，需要尽快的开始回答，也就是说要尽快生成输出第一个token，之后的token，需要能跟上人的阅读速度；而对于代码生成类的应用，则需要更快的端到端生成速度，以支持实时的代码提示。 目前的大模型推理服务系统，都是以吞吐（throughput）为标准来优化的，也就是单位时间服务的用户请求数（request per second, rps）。这个指标，也被用作推理成本优化的一个目标，因为更高的吞吐，意味着可以用更少的GPU时间服务更多的用户请求。 作者提出，简单的用吞吐作为指标是不够的。在实际场景中，应用对推理服务有不同的质量目标（service level objectives, SLO），对于LLM推理服务而言，最重要的有两个SLO： TTFT (Time To First Token): LLM生成第一个token需要的时间 TPOT (Time Per Output Token): LLM生成两个token之间的平均延迟 显然，TTFT表示LLM多久开始回答，而TPOT表示LLM的语速。 作者认为，LLM推理服务的质量应该看Goodput，可以理解为“有效吞吐”。Goodput的意思是： 对于每个分配的GPU，在满足SLO目标的前提下（例如 90% TTFT < 200ms，90% TPOT < 50ms），所能达到的最大吞吐。更高的Goodput，意味着每个请求的服务成本更低。 maximum request rate that can be served adhering to the SLO attainment goal (say, 90%) for each GPU provisioned – higher per-GPU goodput directly translates into lower cost per query. 更高的throughput，并不一定意味着更高的goodput。 为什么生成第一个token会花费更久呢？ 因为在服务用户的时候，LLM需要把用户的历史对话作为上下文，加上用户当前的问题（请求），作为prompt去推理，因此生成第一个token需要计算很长的prompt。而后续的token，因为LLM推理普遍采用KV cache缓存前一次生成的中间结果，避免重复计算，每次生成token计算量要比第一个token小得多。 关于KV cache，简单说几句：不要把它混淆为Key Value，这里的KV指的是Transformer的K，V矩阵。KV cache的原理是，自回归的LLM在生成时，每次生成的上下文，和上一次生成只差一个token，因此有大量计算是重复的。如果把上一次生成时的中间结果（主要是K，V矩阵）记下来，那么下一次生成的时候就可以避免重复计算，大大降低推理成本。这个技术目前已经是标配了，基本上所有的LLM推理都会用到它。 ...

对于内核、驱动、嵌入式系统等底层开发来说，C语言的bit field（位域）和union（联合）都是常用的特性。 位域可以让我们在结构体中指定某些成员占多少位，这在同硬件打交道的时候特别有用。例如硬件要求某个32位的消息里，第31位是flag，其余是value，用位域定义的数据结构： typedef struct msg_t { ​ uint32_t flag : 1; uint32_t value : 31; } msg_t; 在程序里可以直接操作结构体成员那样访问flag和value，而不用手动去对32位消息进行位操作，这些编译器都给我们做了。 我们还可以加上联合（union），使得我们既可以访问里面的成员，也可以按照一个32位数访问整个消息： typedef struct msg_fields_t { uint32_t flag : 1; uint32_t value : 31; } msg_fields_t; ​ typedef struct msg_t { union { uint32_t raw; msg_fields_t fields; }; } msg_t; union告诉编译器，raw和fields这两个成员在结构体里占用同样的内存地址。因为这两个成员都是32位，因此raw就是整个32位的消息，而通过fields可以访问该消息的flags和value。 但是，在同时使用union和bit field的时候要注意，union和bit field如果互相套在一起，编译器产生的内存排列可能和你想的不一样！ ...

In early 2023, Intel announced the discontinuity of Optane products (including SSD and memory). While not quite surprising considering their business environment, it’s still a bit of disappointment to me. As we are closing to the end of 2023, I decided to take some time and write down some of my reflections on Optane’s journey. [Disclaimer] All contents & discussions in this article are just my personal opinions and do not represent any organization or institution. ...

接前文，继续聊量子信息的不可克隆性这个话题。在前文中，我们用最简单的CNOT门为例子，演示了为什么CNOT量子电路只能复制经典信息，而并不能复制处于一般态的量子位。今天把这个讨论扩展到一般的情况，来证明 复制量子态的机器不可能存在 。 基本思路是用反证法。假设我们有个能复制一个量子位的机器，那么这个机器构成的系统，至少包含这些部分： 被克隆的量子位， \(|\psi\rangle = \alpha|0\rangle + \beta|1\rangle\) 辅助量子位， \(|\phi\rangle\) 机器本身的状态 \(|A\rangle\) ，初始状态用 \(|A_i\rangle\) 表示 既然这个机器是量子电路构成的，这个“克隆”过程也必然是一个幺正变换。把这个幺正变换记作U，那么我们要达到的是这样的一个变换过程： \begin{matrix} U |\psi\rangle |\phi\rangle |A_i\rangle \rightarrow |\psi\rangle |\psi\rangle |A_{f\psi}\rangle \end{matrix} 也就是输入的 \(|\psi\rangle\) 被复制成了2个，而机器的状态由初始的 \(|A_i\rangle\) 变成了某个终态，这个终态必然是依赖于输入 \(|\psi\rangle\) ，所以记作 \(|A_{f\psi}\rangle\) 。 显然，如果输入是 \(|0\rangle\) 或 \(|1\rangle\) 的话，我们有： \begin{matrix} U |0\rangle |\phi\rangle |A_i\rangle \rightarrow |0\rangle |0\rangle |A_{f0}\rangle \\ U |1\rangle |\phi\rangle |A_i\rangle \rightarrow |1\rangle |1\rangle |A_{f1}\rangle \\ \end{matrix} 那么如果输入是一般的量子态呢？也就是 \(|\psi\rangle = \alpha|0\rangle + \beta|1\rangle\) 把它代入到前面的变换过程里： \begin{matrix} U |\psi\rangle |\phi\rangle |A_i\rangle \\ = U (\alpha|0\rangle + \beta|1\rangle) |\phi\rangle |A_i\rangle \\ \rightarrow \alpha U |0\rangle |\phi\rangle |A_{f0}\rangle + \beta U |1\rangle |\phi\rangle |A_{f1}\rangle \\ = \alpha |0\rangle |0\rangle |A_{f0}\rangle + \beta |1\rangle |1\rangle |A_{f1}\rangle \\ = \alpha |00\rangle |A_{f0}\rangle + \beta |11\rangle |A_{f1}\rangle \\ \end{matrix} 但是，这是不是我们想要的“克隆”效果呢？显然不是啊！我们要的“克隆”变换，变换后的状态应该是这样的： ...

如果你关注过量子通信或量子信息的动态，应该会经常听到量子信息的“不可克隆性”这个概念。那么这个概念是怎么来的？今天就来聊一聊。 先从一个简单的例子出发。从以前对CNOT门的讨论，它似乎可以用来“复制”信息： 看起来当辅助量子位是 \(|0\rangle\) 的时候，输出就得到了两个 \(|x\rangle\) ，真的是这样吗？ 实际上，CNOT门只能复制经典信息（也就是输入为 \(|0\rangle\) 或 \(|1\rangle\) 的情况）。如果输入是一般状态 \(|\psi\rangle=a|0\rangle+b|1\rangle\) ，CNOT并不能复制它！ 咱们来具体推导一下。首先在输入端，要复制的量子位是 \(a|0\rangle+b|1\rangle\) ，辅助量子位 \(|0\rangle\) ，合起来输入端状态就是 \begin{matrix} (a|0\rangle + b|1\rangle)|0\rangle = a|00\rangle + b|10\rangle \end{matrix} CNOT的作用是当第一个量子位为1的时候翻转第二个量子位，所以我们在输出端得到的状态是 \begin{matrix} a|00\rangle + b|11\rangle & (1) \\ \end{matrix} 但是，我们要的是在输出端复制 \(|\psi\rangle\) ，也就是在输出端得到 \(|\psi\rangle|\psi\rangle\) ，这个状态展开写就是这样： \begin{matrix} |\psi\rangle|\psi\rangle = (a|0\rangle+b|1\rangle)(a|0\rangle+b|1\rangle) & \\ = a^2|00\rangle + ab|01\rangle + ab|10\rangle + b^2|11\rangle & (2) \\ \end{matrix} 比较一下(1)和(2)，只有当 \(ab=0\) ，也就是要复制的量子位为 \(|0\rangle\) 或 \(|1\rangle\) 时，这两个式子才有可能相等，而在一般情况下，(1)和(2)不可能相等。 这个推导告诉我们，CNOT组成的“复制”电路，只能复制经典比特，不能复制处于一般态的量子位。 ...

之前聊了不少量子计算的算法，今天换个话题，回到量子计算的一个根本问题，聊聊为什么量子计算机这么难制造。 经典计算机里的晶体管，工作时状态是确定的0或1，这样的可靠性是因为晶体管的状态并不取决于单个电子，而是许多电子的平均。这样一来，即使有少数电子的状态受到干扰翻转了（例如电子在线路中逃逸了），也不影响整个晶体管的状态。这也是经典计算机能可靠工作的关键。 举个例子来说，假如一个经典计算机里的比特由3个电子的状态表示，每个电子可能处于两种状态之一，记作 \(|\uparrow\rangle\) 和 \(|\downarrow\rangle\) 。在工作的时候，假如某个电子发生了翻转： \begin{matrix} |\uparrow\uparrow\uparrow\rangle \Rightarrow |\uparrow\downarrow\uparrow\rangle \end{matrix} 这种情况并不会造成经典比特的翻转。实际情况里，一个经典比特会由多得多的电子状态来表示，少数电子造成翻转的可能性就更小了，由此保证了经典计算机的可靠性。 但是，这个性质也决定了经典计算机的『经典』特性，使它无法表现出『量子』的一面。 设想一下，假如我们想用两个经典比特构造一个量子相干态： \begin{matrix} |\uparrow\uparrow\uparrow\rangle |\downarrow\downarrow\uparrow\rangle + |\downarrow\downarrow\downarrow\rangle |\uparrow\uparrow\uparrow\rangle \end{matrix} 在逻辑上，这个状态可以写成 \begin{matrix} |L\rangle = |1\rangle |0\rangle + |0\rangle |1\rangle \end{matrix} 假如某个电子翻转了，例如第一个晶体管的状态从 \(|\uparrow\uparrow\uparrow\rangle\) 变成了 \(|\uparrow\uparrow\downarrow\rangle\) ，物理状态发生了变化，但逻辑状态没有变： \begin{matrix} |P\rangle = |\uparrow\uparrow\uparrow\rangle |\downarrow\downarrow\uparrow\rangle + |\downarrow\downarrow\downarrow\rangle |\uparrow\uparrow\uparrow\rangle \\ \Rightarrow |\uparrow\uparrow\downarrow\rangle |\downarrow\downarrow\uparrow\rangle + |\downarrow\downarrow\downarrow\rangle |\uparrow\uparrow\uparrow\rangle \\ \\ |L\rangle = |1\rangle |0\rangle + |0\rangle |1\rangle \\ \Rightarrow |1\rangle |0\rangle + |0\rangle |1\rangle \end{matrix} 您可能会问：这不挺好么？物理上虽然有电子发生了翻转，但逻辑上就像什么也没发生一样！ ...

最近和量子搜索干上了 :-) 聊聊另一个量子搜索的应用——加速NP完全问题的求解。 学计算机朋友的应该都听说过『NP完全问题』。 所谓NP完全问题（NP-complete problems），不是指某一个，而是指一类问题，它们的共同特征是，可以快速验证给定的答案是否正确（verify the solution），但是要找到正确的答案（find the solutions）则很难，目前还没有找到高效（多项式复杂度）的算法。并且这一类问题是可以互相转化的，也就是说如果某一个NP完全问题找到了高效的求解算法，那么所有其他的NP完全问题也都能够高效求解了。 哈密尔顿回路问题（Hamilton cycle problem）就是一个NP完全问题。这个问题是说，给你一个图（有向或无向都可），请你找到一个访问图中所有顶点各一次的回路。这个问题又称为“旅行推销员问题”。 用数学语言来分析，假设这个图有n个顶点 \(v_1, v_2, \dots, v_n\) ，我们要找的是一个包含n个顶点，也就是长度为n的路径。为方便讨论，我们假设允许顶点重复，那么把所有可能的长度为n的路径列出来，总共有 \(n^n\) 种可能，所以整个搜索空间有 \(n^n = 2^{n \log n}\) 个状态。哈密尔顿回路问题，就是要在这个搜索空间里找出符合条件的答案。 显然，给定一个路径，我们很容易就能判断它是否是哈密尔顿回路，但是要从给定的图找到一个哈密尔顿回路，目前还没有发现高效（多项式）的算法。在经典计算机上，寻找哈密尔顿回路的复杂度是： \begin{matrix} O(2^{n \lceil \log n \rceil}) \end{matrix} 那么在量子计算机上，是否可以做的更好呢？答案是肯定的。量子计算机可以对这个问题实现平方根（square root）加速： \begin{matrix} O(2^{n \lceil \log n \rceil / 2}) \end{matrix} 接下来看看量子计算机是怎么做到的。 首先我们得有个函数判断给定的路径是否是哈密尔顿回路： \begin{matrix} f(v_1 v_2 \dots v_n) = \left\{ \begin{array}{ll} 1 && v_1 v_2 \dots v_n \verb= is a Hamilton cycle= \\ 0 && otherwise \end{array} \right. \end{matrix} 然后，把路径 \(v_1 v_2 \dots v_n\) 看作是量子电路的一个状态 \(|v\rangle\) 。比如，给某个顶点编号1到n，那么每个状态就是由n个1到n的数字来组成。显然要用二进制表示这样的状态，需要的肯定不止n比特，而是需要 \(n\log n\) 比特。因此在量子电路里需要 \(n\log n\) 个量子位来表示状态。 ...

前文《量子搜索》讨论了Grover算法，今天来讨论量子搜索的一个扩展问题——量子计数。 在量子搜索里，我们有一个搜索空间以及一个判断函数f，给定一个状态，f告诉我们它是不是要找的目标状态。Grover算法把f包装成一个G变换，经过多次迭代后测量，可以以任意高的概率得到答案（目标状态）。 量子计数的问题和搜索有点类似，但它关注的是答案（目标状态）的数量：已知在N个项的搜索空间里有若干个（M个）答案，但是答案的数量M未知，如何高效的确定有多少个答案（也就是M的值）？ 如果用经典计算机来解决这个问题，就必须遍历整个搜索空间，也就是要查询 \(O(N)\) 次。 如果用量子计算机的话，我们只需要用 \(O(\sqrt N)\) 次查询。相对经典计算机，这是一个多项式级别的加速（polynomial improvement）。之前讨论的Shor算法对因式分解问题有指数级加速，量子计数相比没那么耀眼，但也是一个显著的进步了。 量子计数算法的思路其实很简单：把Grover算法中的G变换看作是相位估计里的U，放到量子相位估计电路里，根据估计出来的相位，就能得到目标状态的数量（M的值）。 在《Grover算法的可视化》一文中，我们知道G变换其实是一个旋转变换，画个图理解一下： 在这个图里， \(|\alpha\rangle\) 表示所有非目标状态的叠加，而 \(|\beta\rangle\) 是所有目标状态的叠加。显然它们互相是正交的，如果用它们作为两个轴张成一个平面，那么Grover算法里的G变换就是把输入向量 \(|\psi\rangle\) 朝着 \(|\beta\rangle\) 轴旋转一个角度 \(\theta\) 。因此G变换可以写成这样的矩阵： \begin{bmatrix} \cos\theta && -sin\theta \\ \sin\theta && \cos\theta \end{bmatrix} 不难证明， \(|\alpha\rangle\) 和 \(|\beta\rangle\) 是G的两个本征向量，并且它们对应的本征值分别是 \(e^{i\theta}\) 和 \(e^{i(2\pi-\theta)}\) 。如果你有兴趣，可以拿纸笔验证一下。:-) 总之，这个G变换可以作为量子相位估计里的U来使用。 把Grover算法里的G变换放到量子相位估计里： 假设搜索空间大小N可以用n位二进制数表示，这里输入用了n+1位，也就是把搜索空间扩大了一倍。为什么要这么做呢？ 还记得前文讨论Grover算法有个特殊情况吗？就是目标状态（答案）的数量M超过N的一半，这种情况下Grover算法的性能反而会变差，因为每次旋转的角度太大了，转过头了。解决的办法，就是把搜索空间扩大一倍，确保目标状态的数量少于搜索空间的一半。这里用了同样的思路，因为我们不知道M是多少，干脆先在输入端把N扩大成2N，确保M少于搜索空间的一半。 另一个寄存器需要的量子位数目t，是由我们需要的精度和成功率来决定。例如，假如我们需要相位估计达到m比特的精度，并且成功率大于 \(1-\epsilon\) ，那么t可以这样估算： \begin{matrix} t = m + \lceil \log (2+\frac{1}{2\epsilon}) \rceil \end{matrix} 运行这个电路，在右边测量得到相位估计的结果，也就是 \(\theta\) 的近似值。 而根据Grover算法的原理和G变换的性质，我们知道： \begin{matrix} \sin \frac{\theta}{2} = \sqrt \frac{M}{2N} \end{matrix} 因此： ...

在前文《量子相位估计》里，我们讨论了量子相位估计算法，它也是很多量子算法能有指数级加速的关键。今天来讨论量子相位估计的另一个应用：求解给定幺正变换的平方根。 假如我们有一个幺正变换 \(U\) ，求解它的k次方 \(U^k\) 很容易，只要把k个 \(U\) 连起来就行，但是如果要求它的平方根 \(U^{1/2}\) 呢？事情就没那么简单了。今天来讨论一下，如何利用量子相位估计来求给定幺正变换的平方根，或者说，构造一个新的幺正变换，使它的平方等于给定的幺正变换。 先回顾一下什么是量子相位估计。 假如我们有一个幺正算符 \(U\) ， \(|u\rangle\) 是它的一个本征矢量，对应的本征值是 \(e^{i\phi}\) （ \(\phi\) 在0到 \(2\pi\) 之间）： \begin{matrix} U|u\rangle = e^{i\phi}|u\rangle \end{matrix} "量子相位估计"问题，就是从幺正算符 \(U\) 和 \(|u\rangle\) ，估算相应的本征值 \(e^{i\phi}\) 里的相位 \(\phi\) 。 量子相位估计的电路如下，输入 \(|u\rangle\) 是U的一个本征向量，在输出端测量，就能得到其本征值的相位 \(\psi=\phi/2\pi\) 的 n位二进制近似 。 你可能注意到，这里的输入 \(|u\rangle\) 是U的 一个 本征向量。但是，U可能有很多个本征向量，对不对？ 如果这个相位估计电路输入的不是某一个本征向量，而是U所有本征向量的叠加呢？右边输出会得到什么？也就是说，如果左边的输入是U的所有本征向量 \(|u_j\rangle\) 的叠加： \begin{matrix} |\psi\rangle = \sum_j \alpha_j |u_j\rangle \end{matrix} 猜猜右边会得到啥？ 答案很容易猜到，既然左边的输入是本征向量的叠加，那么右边的输出，就是对应的相位估计结果的叠加： \begin{matrix} U|\psi\rangle = \sum_j \alpha_j e^{i\phi_j} |u_j\rangle \end{matrix} 也就是说，如果在右边测量，会得到某一个本征向量 \(|u_j\rangle\) 的相位估计，其概率取决于它在输入的叠加态里的强度 \(|\alpha_i|^2\) 。 ...

线性独立 如果一组矢量 \(|\alpha_1\rangle, \dots, \alpha_m\rangle\) 满足： \begin{matrix} c_1|\alpha_1\rangle + c_2|\alpha_2\rangle + \dots + c_m|\alpha_m\rangle = 0 \end{matrix} 当且仅当 \begin{matrix} c_1 = c_2 = \dots = c_m = 0 \end{matrix} 那么称这组矢量就是线性独立的。 内积 模 柯西-施瓦茨不等式 正交归一 维数 Gram-Schmidt分解，构造正交归一基方法 线性算符 线性算符之积 完备性关系 线性算符的矩阵表示 Pauli矩阵 投影算符 多维子空间中的投影算符 本征值，本征矢量 厄米算符(Hermitian?) 逆算符 幺正算符 ...

之前的Shor算法系列，其实还有个相关的坑，就是“量子相位估计” (Phase Estimation)，今天也来填一下。:-) 什么是“量子相位估计”？ 假如我们有一个幺正算符 \(U\) ，他的本征矢量是 \(|u\rangle\) ，本征值是 \(e^{i\phi}\) （ \(\phi\) 在0到 \(2\pi\) 之间）。 "量子相位估计“问题，就是从幺正算符 \(U\) 和它的本征矢量 \(|u\rangle\) ，估算它的本征值 \(e^{i\phi}\) 里的相位 \(\phi\) ： Estimate phase \(\phi\) of an eigenvalue of an unitary operator \(U\), given its eigenvector \(|u\rangle\). 量子相位估计算法 既然幺正算符 \(U\) 的本征矢量是 \(|u\rangle\) ，并且其对应的本征值是 \(e^{i\phi}\) ，那么根据本征矢量的定义： \begin{matrix} U|u\rangle = e^{i\phi}|u\rangle \end{matrix} 那么如果对 \(|u\rangle\) 进行多次U变换，不难推导出： \begin{matrix} U^k|u\rangle = e^{ik\phi}|u\rangle \end{matrix} 所以多次对 \(|u\rangle\) 进行 \(U\) 变换，得到的状态仍然是 \(|u\rangle\) ，只不过给它增加了一个全局相位。 我们可以从 \(U\) 制备出一组（n个）这样的幺正变换： \(U, U^2, U^4, U^8, \dots, U^{2^{n-1}}\) ...

今天来填个坑 :-) 前面Shor算法系列里大量用到的“量子傅立叶变换”，具体要怎么实现？这次来详细讨论一下。 量子傅立叶变换 前文说过，量子傅立叶变换QFT是这么一块电路： 同样根据前文，当输入n个量子位的基态 \(|j\rangle\) 时，输出可以写成： \begin{matrix} QFT|j\rangle = \\ \frac{1}{\sqrt{2^n}} \otimes_{l=1}^n \left[ |0\rangle + e^{2\pi ij/2^l} |1\rangle \right] \\ = \frac{1}{\sqrt{2^n}} \left( |0\rangle + e^{2\pi i 0.j_0}|1\rangle \right) \left( |0\rangle + e^{2\pi i 0.j_1j_0}|1\rangle \right) \dots \left( |0\rangle + e^{2\pi i 0.j_{n-1}j_{n-2}\dots j_0}|1\rangle \right) \\ \end{matrix} 我们的任务是用基本量子电路门构造这样的变换。 基本构件：受控旋转门 就像搭积木一样，量子傅立叶变换的电路是由很多基本组件构成的。其中最重要的一个组件是“受控旋转门” \(R_k\) ： 这个量子门和CNOT门差不多，有一个控制输入，当控制输入是 \(|0\rangle\) 的时候，输入状态原样输出；而如果控制输入是 \(|1\rangle\) ，就对输入状态绕Z轴旋转一定的角度。旋转多少角度呢？这是由门的参数k决定的，具体来说就是 \(2\pi/2^k\) 。换句话说， \(R_k\) 的作用就是当控制输入为 \(|1\rangle\) 时，给输入作这样的一个变换： \begin{bmatrix} 1 & 0 \\ 0 & e^{\frac{2\pi i}{2^k}} \end{bmatrix} 量子傅立叶变换电路 有了受控旋转门 \(R_k\) ，接下来我们就可以来搭建量子傅里叶变换电路了！ ...

随手翻到一个Simon问题，今天就来聊聊它。Simon问题和之前讨论的Deutsch问题有点类似，也是一个用量子计算机能够达到指数级加速的问题。 什么是Simon问题？ 和Deutsch问题类似，假设有人给我们一个函数f(x)，内部实现未知，只知道它输入n位二进制数，输出也是n位二进制数。用数学语言描述就是这样： \begin{matrix} f: \{ 0,1 \}^n \rightarrow \{ 0,1 \}^n \end{matrix} 然后又知道存在某个数a，使得 \(f(y)=f(x)\) 当且仅当 \(y=x \oplus a\) ，这个a也称作函数f(x)的周期。为方便讨论，假设a不是0。 Simon问题要解决的，就是求解这个周期a的值。 在经典计算机上，这是一个困难的问题。因为f(x)是未知的，我们能做的就是从0到 \(2^n-1\) 中，每次选一个数作为输入计算f(x)，直到发现重复的输出。最坏情况下，需要遍历超过一半的输入，即 \(2^{n-1}+1\) 次。根据Birthday Paradox，这个问题在经典计算机上需要的查询次数（时间复杂度）是 \(O(2^{n/2})\) 。 而在量子计算机上，我们只需要运行电路 \(O(n)\) 次就能以任意高的成功率得到结果。相对经典计算机，这是 指数级别 的加速！ Simon问题的量子算法 和之前的其他量子算法一样，首先我们得把函数f(x)包装成可逆变换 \(U_f\) ： 然后放到Simon问题的量子电路里： 接下来我们来详细分析一下这个量子算法的过程。 t0时刻 第一个寄存器经过n位的H变换，变成 \(|0\rangle\) 到 \(|2^n-1\rangle\) 的叠加态，即 \(\frac{1}{2^{n/2}}\sum_{x=0}^{2^n-1}|x\rangle\) 。 第二个寄存器状态是 \(|0\rangle\) 。 所以合起来，t0时刻的状态是 \(\frac{1}{2^{n/2}}\sum_{x=0}^{2^n-1}|x\rangle|0\rangle\) t1时刻 经过 \(U_f\) 变换，两个寄存器进入纠缠态，第一个寄存器还是 \(\frac{1}{2^{n/2}}\sum_{x=0}^{2^n-1}|x\rangle\) ，第二个寄存器变成了 \(|f(x)\rangle\) 。所以系统状态是： \(\frac{1}{2^{n/2}}\sum_{x=0}^{2^n-1}|x\rangle|f(x)\rangle\) t2时刻 对第二个寄存器进行测量，使它坍缩到某个值 \(z=f(x_0)\) 。 ...