Fast Toffoli Gate Implementierung

Question

Ich arbeite an einem genetischen Algorithmus mit Toffoli Gates für die Klasse. Ich habe den genetischen Algorithmus, aber es ist ziemlich langsam.

Die Auswertungsfunktion läuft eine Toffoligate-Funktion ~ 10.000 mal pro "Organismus". Mit einer Bevölkerung von 1.000 läuft es pro Generation über 100.000 Mal. Es ist bei weitem der langsamste Teil meines genetischen Algorithmus.

Für meine Implementierung wirkt eine Toffoli Gate auf eine Bitfolge. Jedes Bit hat den Status None, On, Off oder Flip. Nur ein Bit pro Zeichenfolge kann den FLIP-Status haben. Das Toffoli-Gatter dreht das auf FLIP gesetzte Bit um, wenn alle Bits mit dem Zustand ON 1 sind und alle auf OFF gesetzten Bits 0 sind, wobei die None-Bits ignoriert werden.

Für Beispiel

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

Dann wird die Eingabe von "1001" und ein Toffoli-Gatter von "X0- @" würde aussehen wie

1001 
XO-@ 
---- 
0001 

Was eine schnelle Möglichkeit wäre, dies zu implementieren?

Meine erste Implementierung verwendet Bitsets.

#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

Ändern Sie Ihre Gate Darstellung:

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

Und dann können Sie den Betrieb sehr effizient mit Bit-Operationen implementieren:

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