C++

Forum

 
Fast Toffoli Gate Implementation

RadWayne (97)
I'm working on a genetic algorithm using toffoli gates for class. I've got the genetic algorithm working, but it's pretty slow.

The evaluation function runs a toffoli gate function ~10,000 times per "organism". With a population of 1,000 its running over 100,000 times per generation. It is by far the slowest part of my genetic algorithm.

https://en.wikipedia.org/wiki/Toffoli_gate
For my implementation, a toffoli gate acts on a bit string. Each bit has a state of None, On, Off, or Flip. Only one bit per string can have the FLIP state. The toffoli gate flips the bit set to FLIP, if all bits with the state ON are 1, and all bits set to OFF are 0, ignoring the None bits.

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

Then the input of "1001" and a toffoli gate of "X0-@" would look like

1001
XO-@
----
0001


What would be a fast way to implement this?

My initial implementation uses bitsets.
*Updated with comments and removed unnecessary new call.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#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);
}
Last edited on
cire (8284)
I don't know about the data structure itself, but calling new unnecessarily for every invocation of toffoli has a certain smell to it.
RadWayne (97)
That was leftover from a previous implementation. It hadn't occurred to me that it was no longer needed.
Without creating on object unnecessarily, it is faster, but still not fast. What else could be improved?
Topic archived. No new replies allowed.