CN108932388B - 一种基于量子叠加态的模2n减法器设计方法 - Google Patents

Abstract

一种基于量子叠加态的模2ⁿ减法器设计方法，所述方法利用基本量子受控门实现量子半减器和复位器、量子全减器和复位器的设计方法，以及由量子半减器、量子全减器和复位器构成n位量子模2ⁿ减法器的设计方法；最后利用设计好的模2ⁿ减法器实现基于量子叠加态的模2ⁿ减法运算。本发明解决了量子叠加态的量子模2ⁿ减法运算问题，设计了一个基于量子叠加态的量子模2ⁿ减法器。本发明体现了量子信息处理在信号处理的高效性：只需14n‑13个基本操作就可实现2^m个n位整数模2ⁿ减法运算，而用经典计算机实现相应的加法运算需要O(n2^m)基本操作。摘要附图本发明n量子比特的量子模2ⁿ减法器的量子线路图。

Description

一种基于量子叠加态的模2n减法器设计方法

技术领域

本发明涉及一种基于量子叠加态的模2ⁿ减法器设计方法，属量子线路设计技术领域。

背景技术

模2ⁿ减法表示为

MS(b-a)＝sign(b-a)×[(b-a)mod 2ⁿ] (1)

其中a,b是n位的正整数。当b＜a时，sign(b-a)＝-1，当b≥a时，sign(b-a)＝1。(b-a)mod 2ⁿ是(b-a)对2ⁿ进行求模运算，运算规则如下

在量子计算中，信息单元用量子比特表示，它有两个基本量子态|0>和|1>，基本量子态简称为基态。一个量子比特可以是两个基态的线性组合，常被称为叠加态，可表示为|ψ>＝a|0>+b|1>，其中a和b是两个复数。

张量积是将小的向量空间合在一起，构成更大向量空间的一种方法，用符号

表示。对于两个基态|u>和|v>，它们的张量积

常用缩写符号|uv>，|u>|v>或|u,v>表示，例如对于基态|0>和|1>，它们的张量积可表示为：

对于矩阵U的n次张量积

可简写成

对于量子态|u>的n次张量积

也可简写成

量子线路可以由一序列的量子比特门构成，在量子线路的表示图中，每条线都表示量子线路的连线，量子线路的执行顺序是从左到右。量子比特门可以方便的用矩阵形式表示X(非门)，V、V⁺和单位门是三个常用的单量子比特门，它们的矩阵表示分别为：

其中i是虚数单位。

最重要的多量子比特门是受控U门，由控制量子比特和目标量子比特，当控制位为1时，用黑点表示，当控制位为0时，用白点表示。当U＝X，V,V⁺，此时受控U门分别称为受控非门，受控V门，受控V⁺门，它们的符号表示如图1所示。

可以用n量子比特来表示一个小于2ⁿ整数：|b_n-1b_n-2...b₀>，其中b_h∈{0,1},h＝0,...,n-1。

进一步，n+m量子比特态

可以存储一个大小为2^m的列向量：

其中b(j)是一个n位整数，j＝0,...,2^m-1，n和m都是正整数。

量子线路的性能指标为线路的复杂度。线路的复杂度是指线路中受控非门，受控V门，受控V⁺门的总的数量。

发明内容

本发明的目的是，为了解决量子叠加态的量子减法运算问题，提出一种基于量子叠加态的模2ⁿ减法器设计方法。

本发明实现的技术方案如下，一种基于量子叠加态的模2ⁿ减法器设计方法，所述方法利用基本量子受控门实现量子半减器和复位器、量子全减器和复位器的设计方法，以及由量子半减器、量子全减器和复位器构成n位量子模2ⁿ减法器的设计方法；最后利用设计好的模2ⁿ减法器实现基于量子叠加态的模2ⁿ减法运算。所述基本量子受控门包括受控非门、受控V门和受控量子全加器V⁺门。

所述量子半减器和复位器的设计方法如下：

利用四个受控门实现量子半减器设计线路，用符号Q表示；四个受控门包括一个受控非门、二个受控V门和一个受控V⁺门；这四个受控门的连接顺序为：受控V⁺门、受控V门、受控非门、受控V门。

将量子半减器应用到量子态|c_i>|b_i>|a_i>，得到：

其中

是异或操作，c_i,b_i,a_i∈{0,1}，

当|c_i>＝|0>时，由上式可知量子半减器实现减法(b_i-a_i)，其中输出的第一个量子比特

存储减法(b_i-a_i)的借位信息，输出的第二个量子比特

存储的是减法的差；

为了将减法运算后的辅助量子位复位到初始状态，设计量子半减器的复位器，由5个受控门组成，用符号Q_o表示；五个受控门包括二个受控非门、二个受控V门和一个受控V⁺门；这五个受控门的连接顺序为：受控V⁺门、受控V门、受控非门、受控V门、受控非门。

将量子半器的复位器应用到量子态

得到：

其中

是异或操作，c_i,b_i,a_i∈{0,1}，

由式Q(|c_i>|b_i>|a_i>)可知量子半减器的复位器将

复位为|c_i>；

所述量子半减器的复杂度为4，相应的复位器为5。

所述量子全减器和复位器的设计方法如下：

利用六个受控门设计量子全减器设计线路，量子全减器用符号S表示；六个受控门包括二个受控非门、三个受控V门和一个受控V⁺门；这六个受控门的连接顺序为:受控V门、受控非门、受控V门、受控非门、受控V⁺门、受控V门。

将量子全减器应用到量子态|c_i>|b_i>|a_i>|c_i-1>，得到：

其中

是异或操作，c_i,b_i,a_i,c_i-1∈{0,1}，

当|c_i>＝|0>时，由上式可知量子全减器实现减法(b_i-a_i-c_i-1)，其中输出的第一个量子比特

存储减法(b_i-a_i-c_i-1)的借位信息，输出的第二个量子比特

存储的是减法的差；

为了将减法运算后的辅助量子位复位到初始状态，量子全减器的复位器，由八个受控门组成，用符号S₁表示；八个受控门包括四个受控非门、三个受控V门和一个受控V⁺门；这八个受控门的连接顺序为：受控V门、受控非门、受控V门、受控非门、受控V⁺门、受控V门、受控非门、受控非门。

将量子全减器的复位器应用到量子态

得到：

其中

是异或操作，c_i,b_i,a_i,c_i-1∈{0,1}，

由公式(6)可知量子全减器的复位器将

复位为|c_i>；

所述量子全减器的复杂度为6，相应的复位器为8。

所述n量子比特的量子模2ⁿ减法器的设计方法如下：

利用量子半减器、量子全减器及相应的复位器设计n量子比特的模2ⁿ减法器的线路，n量子比特的模2ⁿ减法器用符号M_U表示；

n量子比特的模2ⁿ减法器由(n-1)个量子全减器、(n-2)个量子全减器的复位器、1个量子半减器和1个量子半减器的复位器组成，它实现两个n位整数的模2ⁿ减法运算；

假设n位的整数a和b存储在如下两个n量子比特的基态中：

其中，a_n-1a_n-2…a₀和b_n-1b_n-2…b₀分别是整数a和b的二进制表示，a_h,b_h∈{0,1},h＝0,...,n-1；

添加n量子比特的量子基态

最为减法运算的辅助位，并排列顺序得到|0b_{n- 1}a_n-10b_n-2a_n-2…0b₀a₀>作为输入；将模2ⁿ减法器应用到|0b_n-1a_n-10b_n-2a_n-2…0b₀a₀>，得到：

M_U|0b_n-1a_n-10b_n-2a_n-2…0b₀a₀>＝|d_nd_n-1a_n-10d_n-2a_n-2…0d₀a₀>；

其中d_n表示符号位，d_n＝0表示正数，d_n＝1表示负数，d_n-1d_n-2...d₀是整数[(b-a)mod 2ⁿ]的二进制表示，d_h∈{0,1},h＝0,...,n-1。

由上式可知，模2ⁿ减法器实现如下的模2ⁿ减法运算：

实现一个n位整数的量子模2ⁿ减法运算的复杂度为6(n-1)+8(n-2)+4+5＝14n-13,n≥2。

所述基于量子叠加态的模2ⁿ减法器运算实现方法如下：

2^m个元素的列向量

存储在如下(n+m)量子比特的量子叠加态中

其中b(j)是一个n位整数，j＝0,…,2^m-1，n和m都是正整数；

将模2ⁿ减法器M_U和

张量运算得到新的量子运算

其中符号

为张量运算符号。将

应用到下式，

得到：

其中a_n-1a_n-2...a₀、b(j)_n-1b(j)_n-2...b(j)₀和d(j)_n-1d(j)_n-2...d(j)₀分别是整数a、b(j)和d(j)的二进制表示；d(j)＝(b(j)-a)mod 2ⁿ；a_h,b(j)_h,d(j)_h∈{0,1}；h＝0,1,...,n-1,n,m为整数；d(j)_n表示d(j)-a符号位；d(j)_n＝0表示正数；d(j)_n＝1表示负数；

由上式可知，

实现如下的模2ⁿ减法运算：

其中，

即实现如下减法运算：

所述模2ⁿ减法运算，由一个n量子比特的量子模2ⁿ减法器和m量子比特的线构成。

所述模2ⁿ减法运算，用于辅助运算的n-1量子比特基态

与模2ⁿ减法存储运算的量子态|ψ_(a-b)>|a>不会纠缠在一起，因此在模2ⁿ减法运算结束后可移去。

所述模2ⁿ减法运算线路复杂度为14n-13，能并行实现2^m个n位整数模2ⁿ减法运算。

本发明的有益效果是，本发明解决了“量子叠加态的量子模2ⁿ减法运算”问题，设计了一个基于量子叠加态的量子模2ⁿ减法器。本发明体现了量子信息处理在信号处理的高效性：只需14n-13个基本操作就可实现2^m个n位整数模2ⁿ减法运算，而用经典计算机实现相应的加法运算需要O(n2^m)基本操作。本发明的另外一个优点是设计了复位器，使得参与运算的辅助量子基态与保存加法运算结果量子态不会纠缠在一起。

附图说明

图1为本发明量子比特门的名称和符号表示图；

图2为本发明量子半减器的量子实现线路图；

图3为本发明量子半减器的量子实现线路的简图；

图4为本发明量子半减器的复位器的量子实现线路图；

图5为本发明量子半减器的复位器的量子实现线路简图；

图6为本发明量子全减器的量子实现线路图；

图7为本发明量子全减器的量子实现线路简图；

图8为本发明量子全减器的复位器的量子实现线路图；

图9为本发明量子全减器的复位器的量子实现线路简图；

图10为本发明n量子比特的量子模2ⁿ减法器的量子线路图；

图11为本发明n量子比特的量子模2ⁿ减法器的量子线路简图；

图12为本发明基于量子叠加态的模2ⁿ减法运算的量子线路图；

图13为本发明一个基于量子叠加态的模2ⁿ减法运算例子的量子实现线路图。

具体实施方式

本发明的具体实施方式如下：

本实施例一种基于量子叠加态的模2ⁿ减法器设计方法，所述方法利用基本量子受控门实现量子半减器和复位器、量子全减器和复位器的设计方法，以及由量子半减器、量子全减器和复位器构成n位量子模2ⁿ减法器的设计方法；最后利用设计好的模2ⁿ减法器实现基于量子叠加态的模2ⁿ减法运算。

1、本实施例量子半减器和复位器的设计方法

本实施例利用四个受控门实现如图2所示的量子半减器设计线路，它的简图如图3所示，用符号Q表示。四个受控门包括一个受控非门、二个受控V门和一个受控V⁺门。

将量子半减器应用到量子态|c_i>|b_i>|a_i>，得到

其中

是异或操作，c_i,b_i,a_i∈{0,1}，

当|c_i>＝|0>时，由公式(3)可知量子半减器实现减法(b_i-a_i)，其中输出的第一个量子比特

存储减法(b_i-a_i)的借位信息，输出的第二个量子比特

存储的是减法的差。

为了将减法运算后的辅助量子位复位到初始状态，设计如图4的量子半减器的复位器，它由5个受控门组成，包括二个受控非门、二个受控V门和一个受控V+门，其简图如图5所示，用符号Qo表示。

将量子半器的复位器应用到量子态

得到

其中

是异或操作，c_i,b_i,a_i∈{0,1}，

由公式(3)可知量子半减器的复位器将

复位为|c_i>。

分析图2和图4中的量子线路，可得到量子半减器的复杂度为4，相应的复位器为5。

2、本实施例量子全减器和复位器的设计方法

本实施例利用六个受控门实现如图6所示的量子全减器设计线路，它的简图如图7所示，用符号S表示。六个受控门包括二个受控非门、三个受控V门和一个受控V⁺门。

将量子全减器应用到量子态|c_i>|b_i>|a_i>|c_i-1>，得到

其中

是异或操作，c_i,b_i,a_i,c_i-1∈{0,1}，

当|c_i>＝|0>时，由公式(5)可知量子全减器实现减法(b_i-a_i-c_i-1)，其中输出的第一个量子比特

存储减法(b_i-a_i-c_i-1)的借位信息，输出的第二个量子比特

存储的是减法的差。

为了将减法运算后的辅助量子位复位到初始状态，设计如图8的量子全减器的复位器，它由8个受控门组成，包括四个受控非门、三个受控V门和一个受控V⁺门，其简图如图9所示，用符号S₁表示。

将量子全减器的复位器应用到量子态

得到

其中

是异或操作，c_i,b_i,a_i,c_i-1∈{0,1}，

由公式(6)可知量子全减器的复位器将

复位为|c_i>。

分析图6和图8中的量子线路，可得到量子全减器的复杂度为6，相应的复位器为8。

3、本实施例n量子比特的量子模2ⁿ减法器的设计方法

本实施例利用量子半减器、量子全减器及相应的复位器实现如图10所示的n量子比特的模2ⁿ减法器的设计线路，用符号M_U表示。n量子比特的模2ⁿ减法器由(n-1)个量子全减器、(n-2)个量子全减器的复位器、1个量子半减器和1个量子半减器的复位器组成，它实现两个n位整数的模2ⁿ减法运算。

假设n位的整数a和b存储在如下两个n量子比特的基态中：

其中a_n-1a_n-2…a₀和b_n-1b_n-2…b₀分别是整数a和b的二进制表示，a_h,b_h∈{0,1},h＝0，...，n-1。

添加n量子比特的量子基态

最为减法运算的辅助位，并排列顺序得到|0b_{n- 1}a_n-10b_n-2a_n-2...0b₀a₀>作为输入。将模2ⁿ减法器应用到|0b_n-1a_n-10b_n-2a_n-2...0b₀a₀>，得到：

M_U|0b_n-1a_n-10b_n-2a_n-2...0b₀a₀>＝|d_nd_n-1a_n-10d_n-2a_n-2...0d₀a₀> (8)

其中d_n表示符号位，d_n＝0表示正数，d_n＝1表示负数，d_n-1d_n-2...d₀是整数[(b-a)mod 2ⁿ]的二进制表示，d_h∈{0,1},h＝0,...,n-1，[(b-a)mod 2ⁿ]的含义如公式(1)所述。

由公式(8)可知，模2ⁿ减法器实现如下的模2ⁿ减法运算：

因此模2ⁿ减法器的简图可以用图11的符号表示。

分析图10中的量子线路，可得到实现一个n位整数的量子模2ⁿ减法运算的复杂度为6(n-1)+8(n-2)+4+5＝14n-13,n≥2。

4、本实施例基于量子叠加态的模2ⁿ减法器运算实现

由公式(2)可知，2^m个元素的列向量

可以存储如下的(n+m)量子比特的量子叠加态中：

其中b(j)是一个n位整数，j＝0,...,2^m-1，n和m都是正整数。

将模2ⁿ减法器M_U和

张量运算得到新的量子运算

其中符号

为张量运算符号。

将

应用到

得到

其中a_n-1a_n-2…a₀、b(j)_n-1b(j)_n-2...b(j)₀和d(j)_n-1d(j)_n-2...d(j)₀分别是整数a、b(j)和d(j)的二进制表示，d(j)＝(b(j)-a)mod 2ⁿ,a_h,b(j)_h,d(j)_h∈{0,1},h＝0,1,...,n-1,n,m为整数,d(j)_n表示d(j)-a符号位，d(j)_n＝0表示正数，d(j)_n＝1表示负数。

由公式(10)可知，

实现如下的模2ⁿ减法运算：

其中

即实现如下加法运算：

此处，MS(),sign(),mod 2ⁿ如公式(1)所示。

由公式(10)可知，设计如图12中的量子线路可实现公式(12)中的模2ⁿ减法运算，它由一个n量子比特的量子模2ⁿ减法器和m量子比特的线构成。

由公式(11)可知，用于辅助运算的n-1量子比特基态

与模2ⁿ减法存储运算的量子态|ψ_(a-b)>|a>不会纠缠在一起，因此在模2ⁿ减法运算结束后可移去。

分析图12中的量子线路，可得到基于量子叠加态的模2ⁿ减法运算线路复杂度为14n-13，它可并行实现2^m个n位整数模2ⁿ减法运算，这充分体现了本发明实现模2ⁿ减法线路的高效性。

本发明的具体实施如下：

由公式(2)可知，当m＝3,n＝3时，一个2³×1的整数向量[0 1 2 3 4 5 6 7]^T可以存储在如下量子态中：

其中b(j)＝j,j＝0,1,...,7。

设计如图13所示的量子线路实现如下的8个模2³减法运算：

MS([0 1 2 3 4 5 6 7]^T-5)＝[-3 -4 -5 -6 -7 0 1 2]^T (14)

其中[]^T是矩阵的转置。

图13虚框中的量子线路是3量子比特的量子加法器，它由2个量子全加器、1个量子全加器的复位器、1个量子半加器和一个量子半加器的复位器构成，因此线路的复杂度为29，即可以由29个量子基本操作实现一个3位数的模2³减法。由公式(11)可知，图13中的量子线路实现如下的模2³减法运算：

其中：

由公式(15)可知，图13中的量子线路实现公式(14)中的8个模2³减法运算，并且辅助量子比特

不会与|ψ_(b-5)>纠缠在一起。

由于将3量子比特的量子模2³减法器应用到量子叠加态并不需要增加新的量子门，因为图13中的量子线路的复杂度也为29。

Claims (5)

1.一种基于量子叠加态的模2ⁿ减法器设计方法，其特征在于，所述方法利用量子受控门实现量子半减器和复位器、量子全减器和复位器的设计方法，以及由量子半减器、量子全减器和复位器构成n位量子模2ⁿ减法器的设计方法；最后利用设计好的模2ⁿ减法器实现基于量子叠加态的模2ⁿ减法运算；

所述量子半减器和复位器的设计方法如下：

利用四个受控门实现量子半减器设计线路，用符号Q表示；四个受控门包括一个受控非门、二个受控V门和一个受控V⁺门；这四个受控门的连接顺序为：受控V⁺门、受控V门、受控非门、受控V门；

将量子半减器应用到量子态|c_i>|b_i>|a_i>，得到：

其中

是异或操作，c_i,b_i,a_i∈{0,1}，

当|c_i>＝|0>时，由上式可知量子半减器实现减法b_i-a_i，其中输出的第一个量子比特

存储减法b_i-a_i的借位信息，输出的第二个量子比特

存储的是减法的差；

为了将减法运算后的辅助量子位复位到初始状态，设计量子半减器的复位器，由五个受控门组成，用符号Q_o表示，五个受控门包括二个受控非门、二个受控V门和一个受控V⁺门；这五个受控门的连接顺序为：受控V⁺门、受控V门、受控非门、受控V门、受控非门；

将量子半器的复位器应用到量子态

得到：

其中

是异或操作，c_i,b_i,a_i∈{0,1}，

由式Q(|c_i>|b_i>|a_i>)可知量子半减器的复位器将

复位为|c_i>；

所述量子半减器的复杂度为4，相应的复位器为5；

所述量子全减器和复位器的设计方法如下：

利用六个受控门设计量子全减器设计线路，量子全减器用符号S表示；六个受控门包括二个受控非门、三个受控V门和一个受控V⁺门；这六个受控门的连接顺序为：受控V门、受控非门、受控V门、受控非门、受控V⁺门、受控V门；

将量子全减器应用到量子态|c_i>|b_i>|a_i>|c_i-1>，得到：

其中

是异或操作，c_i,b_i,a_i,c_i-1∈{0,1}，

当|c_i>＝|0>时，由上式可知量子全减器实现减法b_i-a_i-c_i-1，其中输出的第一个量子比特

存储减法b_i-a_i-c_i-1的借位信息，输出的第二个量子比特

存储的是减法的差；

为了将减法运算后的辅助量子位复位到初始状态，所述量子全减器的复位器，由八个受控门组成，用符号S₁表示；八个受控门包括四个受控非门、三个受控V门和一个受控V⁺门；这8个受控门的连接顺序为:受控V门、受控非门、受控V门、受控非门、受控V⁺门、受控V门、受控非门、受控非门；

将量子全减器的复位器应用到量子态

得到：

其中

是异或操作，c_i,b_i,a_i,c_i-1∈{0,1}，

由公式(6)可知量子全减器的复位器将

复位为|c_i>；

所述量子全减器的复杂度为6，相应的复位器为8；

所述n量子比特的量子模2ⁿ减法器的设计方法如下：

利用量子半减器、量子全减器及相应的复位器设计n量子比特的模2ⁿ减法器的线路，n量子比特的模2ⁿ减法器用符号M_U表示；

n量子比特的模2ⁿ减法器由n-1个量子全减器、n-2个量子全减器的复位器、1个量子半减器和1个量子半减器的复位器组成，它实现两个n位整数的模2ⁿ减法运算；

假设n位的整数a和b存储在如下两个n量子比特的基态中：

其中，a_n-1a_n-2...a₀和b_n-1b_n-2...b₀分别是整数a和b的二进制表示，a_h,b_h∈{0,1},h＝0,...,n-1；

添加n量子比特的量子基态

最为减法运算的辅助位，并排列顺序得到|0b_n-1a_{n- 1}0b_n-2a_n-2...0b₀a₀>作为输入；将模2ⁿ减法器应用到|0b_n-1a_n-10b_n-2a_n-2...0b₀a₀>，得到：

M_U|0b_n-1a_n-10b_n-2a_n-2...0b₀a₀>＝|d_nd_n-1a_n-10d_n-2a_n-2...0d₀a₀>；

其中d_n表示符号位，d_n＝0表示正数，d_n＝1表示负数，d_n-1d_n-2...d₀是整数[(b-a)mod2ⁿ]的二进制表示，d_h∈{0,1},h＝0,...,n-1；

由上式可知，模2ⁿ减法器实现如下的模2ⁿ减法运算：

实现一个n位整数的量子模2ⁿ减法运算的复杂度为6(n-1)+8(n-2)+4+5＝14n-13,n≥2。

2.根据权利要求1所述的一种基于量子叠加态的模2ⁿ减法器设计方法，其特征在于，所述基于量子叠加态的模2ⁿ减法器运算实现方法如下：

2^m个元素的列向量

存储在n+m量子比特的量子叠加态中

其中b(j)是一个n位整数，j＝0,...,2^m-1，n和m都是正整数；

将模2ⁿ减法器M_U和

张量运算得到新的量子运算

其中符号

为张量运算符号；将

应用到下式，

得到：

其中a_n-1a_n-2...a₀、b(j)_n-1b(j)_n-2...b(j)₀和d(j)_n-1d(j)_n-2...d(j)₀分别是整数a、b(j)和d(j)的二进制表示；d(j)＝(b(j)-a)mod2ⁿ；a_h,b(j)_h,d(j)_h∈{0,1}；h＝0,1,...,n-1,n,m为整数；d(j)_n表示d(j)-a符号位；d(j)_n＝0表示正数；d(j)_n＝1表示负数；

由上式可知，

实现如下的模2ⁿ减法运算：

其中，

即实现如下减法运算：

3.根据权利要求2所述的一种基于量子叠加态的模2ⁿ减法器设计方法，其特征在于，所述模2ⁿ减法运算，由一个n量子比特的量子模2ⁿ减法器和m量子比特的线构成。

4.根据权利要求2所述的一种基于量子叠加态的模2ⁿ减法器设计方法，其特征在于，所述模2ⁿ减法运算，用于辅助运算的n-1量子比特基态

与模2ⁿ减法存储运算的量子态|ψ_(a-b)>|a>不会纠缠在一起，因此在模2ⁿ减法运算结束后可移去。

5.根据权利要求2所述的一种基于量子叠加态的模2ⁿ减法器设计方法，其特征在于，所述模2ⁿ减法运算线路复杂度为14n-13，能并行实现2^m个n位整数模2ⁿ减法运算。

Images