c++ - 快速 Toffoli 门实现

Question

我正在研究一种在类里面使用托福利门的遗传算法。我已经让遗传算法正常工作，但速度很慢。

评估函数对每个“有机体”运行约 10,000 次 toffoli 门函数。人口为 1,000 时，它每代运行超过 100,000 次。这是迄今为止我的遗传算法中最慢的部分。

对于我的实现，一个 Toffoli Gate作用于一个位串。每个位都有 None、On、Off 或 Flip 状态。每个字符串只有一位可以具有 FLIP 状态。如果所有状态为 ON 的位都为 1，并且所有状态为 OFF 的位都为 0，则忽略 None 位，toffoli 门翻转设置为 FLIP 的位。

例如

X = FLIP
@ = ON
O = OFF
- = NONE

然后“1001”的输入和“X0-@”的 toffoli 门看起来像

1001
XO-@
----
0001

什么是快速实现它的方法？

我的初始实现使用位集。

#define BITLEN 10
#define INPUT std::bitset<BITLEN>
#define GATE std::bitset<BITLEN*2>

void toffoli(const GATE* gate, INPUT* state) {
    bool all_conditions = true;
    int flip_index = -1;
    bool set = false;
    for (int i = 0; i < BITLEN; i++) {
        /*a0 and a1 represent the state of A
          11 is FLIP, 10 is ON, 01 is OFF, and 00 is NONE */
        bool A = (*state)[i];
        bool a1 = (*gate)[i*2];
        bool a0 = (*gate)[(i*2)+1];

        if (a1&&a0) {
            flip_index = i;
            set = true;
        }

        //NONE or FLIP have no condition to meet
        //ON means A must be true
        //OFF means A must be false
        //this simplifies to the below if statement
        if (!((!a0&&!a1) || (!A&&a1) || (A&&a0))) {
            all_conditions = false;
            break;
        }
    }

    //if all conditions are met flip the bit with state FLIP
    //check set flag in case gate is not valid
    if (all_conditions && set)
        state->flip(flip_index);
}

Answer 1

改变你的门代表:

struct GATE {
    std::bitset<BITLEN> required_on;
    std::bitset<BITLEN> required_off;
    std::bitset<BITLEN> flip;
};

然后就可以通过位运算非常高效的实现操作了:

void toffoli(const GATE* gate, INPUT* state) {
    if((*state & (gate->required_on | gate->required_off)) == gate->required_on)
        *state ^= gate->flip;
    }
}