论文部分内容阅读
量子计算是一个方兴未艾的研究领域，普遍认为量子计算机可以解决一些经典计算中无法有效解决的问题。量子计算的发展必将对人类社会产生深远的影响。而量子线路，特别是布尔量子线路的研究，对该研究领域中的理论分析和物理实现都非常重要。量子算法通常由量子线路表示出来，设计好的量子线路就意味着能更好地实现量子算法。同时，布尔量子线路的研究也是可逆计算领域的重要研究方向。本文讨论了一些设计与优化布尔量子线路的问题，其目标是以尽可能少的代价构造能实现特定布尔变换的量子线路。
本文的主要内容如下：
1.研究了基于Reed-Muller分解构造布尔量子线路的方法。
布尔函数的Reed-Muller分解形式与Toffoli门有着比较密切的关系，本文通过研究布尔函数Reed-Muller分解形式的一些性质，提出了基于该分解形式为布尔函数构造量子线路的方法。这种方法主要针对不可逆的布尔函数，或者输出位顺序不确定的布尔函数。特别是分析了通过分解项的替换来构造线路的原理，提出的最速下降构造算法可以使用最少的附加位(工作位)，将不可逆布尔函数转化为可逆的布尔函数，而且这个过程与量子线路的构造同步完成。据我所知，这是在该研究领域第一次将不可逆布尔函数的可逆化与线路的构造紧密结合，直接为不可逆布尔函数构造量子线路的研究工作。
2.研究了用遗传算法构造布尔量子线路的方法。
对可逆的布尔函数而言，其实现的是关于计算基的一个变换，而量子门包括Toffoli门和SWAP门等也实现了对计算基的变换。本文通过遗传算法来搜寻基本的量子门序列，使之实现期望中的对计算基的变换。本文设计了一种适应度函数比较客观地反应了线路的适应值，设计并讨论了不同染色体编码方式对算法性能的影响，通过模拟实验验证了算法的有效性。
3.研究了将非邻接量子门转换为邻接量子门的问题。
在物理实现上，对量子位的量子操作通常仅限于相邻或距离比较近的量子。本文讨论了如何引入SWAP门，将量子位的位置进行逻辑交换，以解决将包含非邻接量子门的量子线路转换为只含邻接量子门的量子线路的问题。通过对该问题的分析，本文将其形式简化为一种分层有向无环图中寻找最短路径的问题，并提出了近似算法有效地解决了这个问题。显然，这种线路转化的问题在一般的非布尔量子线路中也存在，因而本文的方法也可以用于其它类型量子线路的转换。
4.实现了辅助设计工具的一个原型系统。
基于Java语言，设计并实现了一个布尔量子线路的辅助设计工具。该原型系统整合了本文的所有研究成果，使用和扩展都很方便，并且与其他研究者的工具有统一的输入输出格式，可以方便地互相交流。特别地，本文提出了一种近似搜索算法，较好地解决了将量子位映射到核磁共振技术中的核子上的问题。