本文为自己在Coursera上课程The Introduction to Quantum Computing第一周中的笔记
有些地方我不用课程里的内容, 更多的用wiki和知乎的内容, 有助于理解
Classical Computing
Information and Computations
先说了一下什么是计算?
课中将计算定义为一个物理过程, 具有有限时间, 有限状态的一个过程
什么是计算的本质，它与编程语言的关系？ - 李遥的回答 - 知乎
再说了一下什么是信息, 如何定量?
nbit信息即2^n种状态(等概率)
赋值需要能量(能量->信息), NOT门不需要能量
最后如果不需要存这个bit了, 我们可以先把左边的活塞推到中间, 再把挡板移除, 粒子会将在活塞推回原处(归还能量), 这个过程叫ERASE(信息->能量)
信息=能量
“物质”，“能量”，“信息” 是同一个东西的三种描述方式么？
Characteristics of Computational Systems
为什么人们没有使用活塞来组成计算机, 而用了其他的方法?
说明计算并不都是完全一样的, 以下为几个最重要的特点.
- Information Capacity (Shannon Formula)
- Speed (switching between the states)
- Universality
对于1, 信息容量越大, 我们就能借此解决更复杂的问题
对于2, 相当于计算过程更快了
对于3, 通用性, 两种方法数羊, 第一种用一段绳子的长度表示, 缺点是可能有累计误差, 且缺乏通用性(比如不能加减乘除), 第二种用一个结来表示一只羊, 失去了连续性, 获得了通用性(能加减乘除).
先撇开3不谈, 详谈12
从电脑的发展史来看, 为什么我们追求越来越小的元件?
- 同样体积能放更多, 我们就能有更多的状态, 即能存放更多的信息(加强1)
- 更小的元器件能有更小的inertia, 即inductance(电感), 我们可以更快的切换状态(加强2)
- 消耗更少的能量
传统晶体管快达到大小极限了, 要想提升就必须更小, 但是小了以后就无法忽视量子效应, 所以下一代计算机必须利用量子效应, 也就只能是量子计算机了
Computability and Algorithms
The Goal of Computation
先重新对Computation下定义, 将其定义为function, 为什么?Because functions have a strict mathematical definition.
提出一个集合, 其中的元素为函数, 函数将自然数映射到0或1
问题:对于每一个函数, 我是否都能计算
首先需要定义什么叫做”我能计算一个函数”?
对于f, 输入是无穷的
So, how can I be sure that I can do that for any of them? I can be sure if I have an algorithm for computing this function.
什么是Algorithm(算法)?
Algorithm is deterministic Turing machine.
邱奇-图灵论题认为如果某种方法（算法）可进行运算(computable)，那么该运算也可被图灵机执行（也可被递归定义的函数或λ函数执行）
考虑一个集合, 其中的元素为函数, 函数将自然数映射到0或1
- How many algorithms are there?
将纸带的程序用二进制编码, 变成01组成的字符串, 将这个字符串前面的0的个数映射到一个整数, 将后面的二进制数映射到一个整数, 所以可得我们有无限的可数的deterministic Turing machine.
- How many function are there?
现在让我们来计算这个集合中一共有多少个函数
我们先对f构造一个形式g(f) = 0,f(1)f(2)f(3)f(4)…….
可以看出, 对于不同的f, 上述的g将一个f映射到[0,1]之间的一个实数, 这证明了函数一共有无限不可数个
- Uncomputable functions?
我们只能有无限的可数的DTM, 但是有无限不可数个函数, 所以其中一定存在不可计算的函数.(实变函数与泛函分析)
同时如果我们随机从这些集合中挑出一个f, 可计算的概率为0.(概率论)
还提到了一个特殊的function是uncomputable
If Church-Turing thesis is correct, then we're deterministic Turing machines and we are not able to analyze every computer program, which means that there can exist, can be written a computer program which we will not be able to understand or to predict its behavior at deterministic computing computer program. Isn't that amazing?
Computational Complexity
我们不谈不可计算的函数, 我们来讨论可计算的函数.
可计算的函数有些容易计算, 有些不容易计算.
比如euler’s path对比hamilton path
比如加法复杂度为O(n), 乘法复杂度为O(n^2)
然后举了几个例子说明P, NP
大数分解说明量子计算机可以解决一些经典计算机无法解决(intractable)的问题, 但是能解决全部的问题吗?
也许不能, 还有一类NP-Hard问题. 如果你有某个神奇的方法能解决一些NP-hard问题, 我们将能解决在多项式时间内解决所有NP问题.
对于NPC问题, 用量子计算机能比传统计算机有更好的解法.(因子分解不在NPC中)
Quantum Computing
part1
1982, Richard Feynman提出我们可以基于量子系统构造下一代计算机.
1985, David Deutsch developed a mathematical model of universal quantum computer.
part2
当系统closed时, 波函数不崩塌
对于BBB的例子, 对于内部来说
|猫>(|上>+|下>) -> |惊猫>|上>+|普猫>|下>
对于外部的我们来说, 后面的状态依旧保持着光子的波函数, 光子仍然有两种可能. 但是猫的波函数分割了. Now it is entangled.(不太懂,原文翻译了)
对于EBBB, 式子变成了|惊猫人>|上>+|普猫人>|下>
提出两个问题:
- 为什么右式的猫无法互相看到, Why the photons do?(为什么光子会这样做?)
- 为什么光子干涉, 人和猫不会干涉?
对于2, 需要两个系统精确匹配才行. 对于人和猫, 太复杂以至于不可能精确匹配, 所以几乎不会干涉
对于1, 下节见
The Multiverse Interpretation of Quantum Mechanics
观测不改变系统的波函数, 观察者改变自身的波函数
对于上节问题1, 一种解释是
instead of believing that this split state of the observer is some kind of unclear wave function, Hugh Everett suggested to consider to believe that these different copies of observer actually exist.
在此理论下, 量子计算机通过不同的branch计算, 然后我们想办法让这些结果干涉(让多世界融合), 再从干涉中得到结果
1000个qubit能有2^1000种分支
尾
下周我们将在数学上学习这些分支如何实现, 也将学习量子计算机, 量子数据, 量子算法的数学模型