量子计算及量子计算的模拟

IT是一个繁荣的行业，寄托着无数人的梦想，充斥着无数的造梦神话。
IT是一个悲催的行业，层出不穷的新概念让人应接不暇，几乎只要有一天不学习，都可能让你寝食不安。

量子计算机是一个炒的比较热的概念，目前还处于上升期，感觉上已经到了爆发的边缘，似乎随时可以呼之欲出。
通常对于量子计算机的理解就是，因为量子计算机的存储特征，可以处理很大的数据，而不是像传统计算机那样只是处理1、0二进制数，因此计算效率更高。从而有可能颠覆现有的计算机架构，甚至现有的所有的加密算法，因为新的、高速的量子计算机的出现，都将因为可能会被快速的解密而失去效用。
这个概念对，但也不全对，并且可能丢失了很多重要的内容。所以这里试图更通俗的解释一番。

传统计算机

说量子计算之前，我们首先要看一下传统的计算机是如何工作的：
体系结构、硬盘、内存、CPU啥的就不用说了，对于计算本身来说，这些体现不出来什么不同。
我们要从CPU来解析，当前不管多么复杂的计算机，计算的根本来自于两个部件：
寄存器 ：用于存储计算用的数据，及计算的结果，比如当前的64位CPU,其实就代表寄存器是由64位二进制数组成的。
逻辑门 ：用于通过各种复杂拼接、组合，从而完成所需的计算。常见的逻辑有：与、或、非。
下面对应传统的计算机，我们说说量子计算机的的原理。

测量

对于传统计算机来讲，测量就是读取，读取又是所有运算的基础，功能没啥好多说的，就是知道寄存器中保存的数值是什么。
量子计算机就复杂了，你应当听说过薛定谔的猫，猫放在箱子里面，箱子里面的放射性元素是否衰变决定着猫的死活，但是在你打开箱子之前，你无法确定，而在打开箱子的瞬间，你实际也改变了箱子的状态，也就是影响了猫的生死，这是量子物理重要的一个特征。
这个特征产生了以下几个重要的概念，或者说重要的特征，这些特征决定了量子计算机的几个重要功能。

叠加态

传统的计算机，无论是寄存器还是存储器，很重要的一个指标就是确定性或者说稳定性。在寄存器方面，其中的每一位(bit),可以确定是1或者是0，64位计算机，寄存器保存的数值最大是2的64次方（2^64）。
量子计算机采用叠加态在寄存器中保存数据，因此同一个寄存器，可能保存了多个数据，这导致量子寄存器可以保存的数值，在同样位数下，比传统计算机保存的数据更多。
当前的量子计算机，每一位(bit),通过叠加态可以保存2对可以互相转换的状态，可以分别表示两位二进制数字。因为两位二进制数共有4个状态，因此量子计算机寄存器指定位长下，可以最大表达4的N次方(4^N)的数字。
而同时因为叠加态及可互相转换的特征，实际上每个指定位长的寄存器，都可能存储2^N个数据，而不是1个，这就是量子计算机的超强存储能力（本项能力只是基于理论设想，在当前的各种量子机实现中，还没有看到资料介绍实际的实现）。

概率

因为叠加态和测量也会对其中数值造成的影响，实际其中的值是由概率决定的。这在量子计算机的制造和算法的研究中，都必须考虑到的问题。

量子密码

因为不可测的特征带来的无法窃听和不可克隆特征，强大的量子计算能力虽然对传统的密码学是一个灾难，但同时也会出现新的、更强大的加密算法。从公开资料上看，我们国家所实现的星-地量子通讯的主要基础就是来自于此。

向量计算和并行计算

因为上面说的叠加态的两对状态，每一个计算实际都转换为了向量运算。现在计算机中最耗能的几项运算：挖矿、图形图像、深度学习等，都是转换成向量和矩阵进行运算的。在传统的计算中，因为二进制的特征，一般复杂度都是O(2^N),而在量子计算机中，因为这种特征，每次是两个数据参与运算，所以复杂度是O(N)。所以运算量不再呈现指数飙升，而是线性增加。
此外，因为叠加态的存在，我们在量子运算中，不必像传统计算一样同时只处理一个数值，而是同时处理叠加的多个数值，实现了真正的并行计算。而传统计算中的并行，不过是把大的并行转换成多个小的时间片再串行而已。这更进一步的提高了运算能力。当然这也需要更复杂的并行算法来支持。

单量子比特门

如同传统计算机一样，量子计算机也是通过逻辑门的运算来完成实际运算的。
同时因为上面说过的那些特征，单量子比特门也有一个很重要的特征：可逆性，我们知道，传统计算机的逻辑门是不可逆的，而单量子比特门的各种运算都可逆；另外一个重要特征就是上面说过的：可并行。
这些常用的门中，包括以下几个：
Hadamard：旋转门
CNOT:受控非门，如果第一位置1，倒置第二位，否则保持不变。
Toffoli：控-控-非门，也叫CCNOT，如果前两位置1，它将倒置第三位，否则所有位保持不变
noop：单位门，等于不做任何操作。
X门：求非变换，NOT门
Z门：相位移动操作
Y门：相当于上面两个门的组合，Y=ZX

量子计算的模拟

目前的情况，除非是在相关单位工作，否则一般的开发人员尚无法亲身体验量子计算机。更谈不上学习量子计算机的开发了。
但是通过上面的介绍你可以发现，除非只做一个拿来主义的使用者，否则这些颠覆性的特征将带来算法上的重大改变，不及早的研究、积累，这真的可能成为程序员的一个“灰犀牛”。
除了在实际的量子计算机上实验，目前也有很多软件提供了量子计算的模拟能力，从而可以尝试自己的算法和实验，达到学习的目的。
微软甚至创立了一种新的语言叫“Q#”来应对将来的量子计算，相信应当也不错，不过最近对于非开源的项目还是有些障碍，所以我们来尝试另外一个工具库DLIB。

环境搭建

首先要假设你已经有了基本的开发环境，比如g++/clang。Ubuntu要保证APT包管理的正常使用，macOS则预先安装好Homebrew包管理。

在Ubuntu16上：

apt install libdlib-dev

在macOS：

brew install dlib

DEMO源码

本源码来自DLIB的Examples代码quantum_computing_ex.cpp，未做任何修改。
代码中使用上面介绍过的这几个逻辑门，实现了两个最常用的基本算法：Grover Search和Shor ECC校验。这两个算法也是相当有名，网上一搜资料大把，我这半瓶水就不画蛇添足了。

// The contents of this file are in the public domain. See LICENSE_FOR_EXAMPLE_PROGRAMS.txt
/*    This is an example illustrating the use of the quantum computing    simulation classes from the dlib C++ Library.    This example assumes you are familiar with quantum computing and    Grover's search algorithm and Shor's 9 bit error correcting code    in particular.  The example shows how to simulate both of these    algorithms.    The code to simulate Grover's algorithm is primarily here to show    you how to make custom quantum gate objects.  The Shor ECC example    is simpler and uses just the default gates that come with the    library.*/

#include <iostream>
#include <complex>
#include <ctime>
#include <dlib/quantum_computing.h>
#include <dlib/string.h>

using namespace std;
using namespace dlib;

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

// This declares a random number generator that we will be using below 
dlib::rand rnd;

// ----------------------------------------------------------------------------------------

void shor_encode (
    quantum_register& reg
)
/*!
    requires
        - reg.num_bits() == 1
    ensures
        - #reg.num_bits() == 9
        - #reg == the Shor error coding of the input register
!*/
{
    DLIB_CASSERT(reg.num_bits() == 1,"");

    quantum_register zeros;
    zeros.set_num_bits(8);
    reg.append(zeros);

    using namespace dlib::quantum_gates;
    const gate<1> h = hadamard();
    const gate<1> i = noop();

    // Note that the expression (h,i) represents the tensor product of the 1 qubit
    // h gate with the 1 qubit i gate and larger versions of this expression
    // represent even bigger tensor products.  So as you see below, we make gates
    // big enough to apply to our quantum register by listing out all the gates we
    // want to go into the tensor product and then we just apply the resulting gate
    // to the quantum register.

    // Now apply the gates that constitute Shor's encoding to the input register. 
    (cnot<3,0>(),i,i,i,i,i).apply_gate_to(reg);
    (cnot<6,0>(),i,i).apply_gate_to(reg);
    (h,i,i,h,i,i,h,i,i).apply_gate_to(reg);
    (cnot<1,0>(),i,cnot<1,0>(),i,cnot<1,0>(),i).apply_gate_to(reg);
    (cnot<2,0>(),cnot<2,0>(),cnot<2,0>()).apply_gate_to(reg);
}

// ----------------------------------------------------------------------------------------

void shor_decode (
    quantum_register& reg
)
/*!
    requires
        - reg.num_bits() == 9
    ensures
        - #reg.num_bits() == 1
        - #reg == the decoded qubit that was in the given input register
!*/
{
    DLIB_CASSERT(reg.num_bits() == 9,"");

    using namespace dlib::quantum_gates;
    const gate<1> h = hadamard();
    const gate<1> i = noop();

    // Now apply the gates that constitute Shor's decoding to the input register

    (cnot<2,0>(),cnot<2,0>(),cnot<2,0>()).apply_gate_to(reg);
    (cnot<1,0>(),i,cnot<1,0>(),i,cnot<1,0>(),i).apply_gate_to(reg);

    (toffoli<0,1,2>(),toffoli<0,1,2>(),toffoli<0,1,2>()).apply_gate_to(reg);

    (h,i,i,h,i,i,h,i,i).apply_gate_to(reg);

    (cnot<6,0>(),i,i).apply_gate_to(reg);
    (cnot<3,0>(),i,i,i,i,i).apply_gate_to(reg);
    (toffoli<0,3,6>(),i,i).apply_gate_to(reg);

    // Now that we have decoded the value we don't need the extra 8 bits any more so
    // remove them from the register.
    for (int i = 0; i < 8; ++i)
        reg.measure_and_remove_bit(0,rnd);
}

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

// This is the function we will use in Grover's search algorithm.  In this
// case the value we are searching for is 257.
bool is_key (unsignedlong n)
{
    return n == 257;
}

// ----------------------------------------------------------------------------------------

template <int bits>
class uf_gate;

namespace dlib {
template <int bits>
struct gate_traits<uf_gate<bits> >
{
    static const long num_bits = bits;
    static const long dims = dlib::qc_helpers::exp_2_n<num_bits>::value;
};}

template <int bits>
class uf_gate : public gate_exp<uf_gate<bits> >
{
    /*!
        This gate represents the black box function in Grover's search algorithm.
        That is, it is the gate defined as follows:
            Uf|x>|y> = |x>|y XOR is_key(x)>

        See the documentation for the gate_exp object for the details regarding
        the compute_state_element() andoperator() functions defined below.
    !*/
public:
    uf_gate() : gate_exp<uf_gate>(*this) {}

    static const long num_bits = gate_traits<uf_gate>::num_bits;
    static const long dims = gate_traits<uf_gate>::dims;

    const qc_scalar_type operator() (long r, long c) const{
        unsigned long output = c;
        // if the input control bit is set
        if (is_key(output>>1))
        {
            output = output^0x1;
        }

        if ((unsigned long)r == output)
            return 1;
        else
            return 0;
    }

    template <typename exp>
    qc_scalar_type compute_state_element (
        const matrix_exp<exp>& reg,
        long row_idx
    ) const{
        unsigned long output = row_idx;
        // if the input control bit is set
        if (is_key(output>>1))
        {
            output = output^0x1;
        }

        return reg(output);
    }
};

// ----------------------------------------------------------------------------------------

template <int bits>
class w_gate;

namespace dlib {
template <int bits>
struct gate_traits<w_gate<bits> >
{
    static const long num_bits = bits;
    static const long dims = dlib::qc_helpers::exp_2_n<num_bits>::value;
}; }

template <int bits>
class w_gate : public gate_exp<w_gate<bits> >
{
    /*!
        This is the W gate from the Grover algorithm
    !*/
public:

    w_gate() : gate_exp<w_gate>(*this) {}

    static const long num_bits = gate_traits<w_gate>::num_bits;
    static const long dims = gate_traits<w_gate>::dims;

    const qc_scalar_type operator() (long r, long c) const{
        qc_scalar_type res = 2.0/dims;
        if (r != c)
            return res;
        else
            return res - 1.0;
    }

    template <typename exp>
    qc_scalar_type compute_state_element (
        const matrix_exp<exp>& reg,
        long row_idx
    ) const{
        qc_scalar_type temp = sum(reg)*2.0/dims;
        // compute this value: temp = temp - reg(row_idx)*2.0/dims + reg(row_idx)*(2.0/dims - 1.0)
        temp = temp - reg(row_idx);

        return temp;
    }
};

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

int main()
{
    // seed the random number generator
    rnd.set_seed(cast_to_string(time(0)));

    // Pick out some of the gates we will be using below
    using namespace dlib::quantum_gates;
    const gate<1> h = quantum_gates::hadamard();
    const gate<1> z = quantum_gates::z();
    const gate<1> x = quantum_gates::x();
    const gate<1> i = quantum_gates::noop();

    quantum_register reg;

    // We will be doing the 12 qubit version of Grover's search algorithm.
    const int bits=12;
    reg.set_num_bits(bits);

    // set the quantum register to its initial state
    (i,i, i,i,i,i,i, i,i,i,i,x).apply_gate_to(reg);

    // Print out the starting bits
    cout << "starting bits: ";
    for (int i = reg.num_bits()-1; i >= 0; --i)
        cout << reg.probability_of_bit(i);
    cout << endl;

    // Now apply the Hadamard gate to all the input bits
    (h,h, h,h,h,h,h, h,h,h,h,h).apply_gate_to(reg);

    // Print out the status
    cout << "after Hadamard gate: ";
    for (int i = reg.num_bits()-1; i >= 0; --i)
        cout << reg.probability_of_bit(i) << " ";
    cout << endl;

    // Here we do the grover iteration
    for (int j = 0; j < 35; ++j)
    {
        (uf_gate<bits>()).apply_gate_to(reg);
        (w_gate<bits-1>(),i).apply_gate_to(reg);

        cout << j << " probability: bit 1 = "<< reg.probability_of_bit(1) << ", bit 9 = "<< reg.probability_of_bit(9) << endl;
    }

    cout << endl;

    // Print out the final probability of measuring a 1 for each of the bits
    for (int i = reg.num_bits()-1; i >= 1; --i)
        cout << "probability for bit "<< i << " = "<< reg.probability_of_bit(i) << endl;
    cout << endl;

    cout << "The value we want grover's search to find is 257 which means we should measure a bit pattern of 00100000001"<< endl;
    cout << "Measured bits: ";
    // finally, measure all the bits and print out what they are.
    for (int i = reg.num_bits()-1; i >= 1; --i)
        cout << reg.measure_bit(i,rnd);
    cout << endl;

    // Now let's test out the Shor 9 bit encoding
    cout << "\n\n\n\nNow let's try playing around with Shor's 9bit error correcting code"<< endl;

    // Reset the quantum register to contain a single bit
    reg.set_num_bits(1);
    // Set the state of this single qubit to some random mixture of the two computational bases
    reg.state_vector()(0) = qc_scalar_type(rnd.get_random_double(),rnd.get_random_double());
    reg.state_vector()(1) = qc_scalar_type(rnd.get_random_double(),rnd.get_random_double());
    // Make sure the state of the quantum register is a unit vector
    reg.state_vector() /= sqrt(sum(norm(reg.state_vector())));

    cout << "state: "<< trans(reg.state_vector());

    shor_encode(reg);
    cout << "x bit corruption on bit 8"<< endl;
    (x,i,i,i,i,i,i,i,i).apply_gate_to(reg); // mess up the high order bit
    shor_decode(reg); // try to decode the register

    cout << "state: "<< trans(reg.state_vector());

    shor_encode(reg);
    cout << "x bit corruption on bit 1"<< endl;
    (i,i,i,i,i,i,i,x,i).apply_gate_to(reg);
    shor_decode(reg);

    cout << "state: "<< trans(reg.state_vector());

    shor_encode(reg);
    cout << "z bit corruption on bit 8"<< endl;
    (z,i,i,i,i,i,i,i,i).apply_gate_to(reg);
    shor_decode(reg);

    cout << "state: "<< trans(reg.state_vector());

    cout << "\nThe state of the input qubit survived all the corruptions in tact so the code works."<< endl;

}

编译的方法如下：
Ubuntu:

g++ -std=c++11 -O3 -o quantum_computing_ex quantum_computing_ex.cpp -l dlib -l cblas

macOS:

g++ -std=c++11 -O3 -o quantum_computing_ex quantum_computing_ex.cpp (pkg-config --cflags --libs dlib-1) -l cblas