| 145 | |
| 146 | |
| 147 | auto getCtrlsAndTargsSwappedToMinSuffix(Qureg qureg, vector<int> ctrls, vector<int> targs) { |
| 148 | |
| 149 | // this function is called by multi-target dense matrix, and is used to find |
| 150 | // targets in the prefix substate and where they can be swapped into the suffix |
| 151 | // to enable subsequent embarrassingly parallel simulation. Note we seek the MIN |
| 152 | // available indices in the suffix, since this minimises the stride of the local |
| 153 | // simulation, improving caching performance. |
| 154 | |
| 155 | // nothing to do if all targs are already in suffix |
| 156 | if (!doesGateRequireComm(qureg, targs)) |
| 157 | return tuple{ctrls, targs}; |
| 158 | |
| 159 | // prepare masks to avoid quadratic nested looping |
| 160 | qindex targMask = getBitMask(targs.data(), targs.size()); |
| 161 | qindex ctrlMask = getBitMask(ctrls.data(), ctrls.size()); |
| 162 | int minNonTarg = getIndOfNextRightmostZeroBit(targMask, -1); |
| 163 | |
| 164 | // prepare map from control qubit to its index in ctrls list (i.e. inverse of ctrls) |
| 165 | std::unordered_map<int,int> ctrlInds; |
| 166 | for (size_t i=0; i<ctrls.size(); i++) |
| 167 | ctrlInds[ctrls[i]] = i; |
| 168 | |
| 169 | // check every target in arbitrary order, modifying our copies of targs and ctrls as we go |
| 170 | for (size_t i=0; i<targs.size(); i++) { |
| 171 | int targ = targs[i]; |
| 172 | |
| 173 | // consider only targs in the prefix substate |
| 174 | if (util_isQubitInSuffix(targ, qureg)) |
| 175 | continue; |
| 176 | |
| 177 | // we will swap targ with minNonTarg, but must first move that it of ctrls |
| 178 | if (getBit(ctrlMask, minNonTarg) == 1) { |
| 179 | |
| 180 | // find and swap that ctrl with the old targ |
| 181 | int ctrlInd = ctrlInds[minNonTarg]; |
| 182 | ctrls[ctrlInd] = targ; |
| 183 | |
| 184 | // update our ctrl trackers |
| 185 | ctrlInds[targ] = ctrlInd; |
| 186 | ctrlInds[minNonTarg] = -1; // erases minNonTarg (for clarity) |
| 187 | ctrlMask = flipTwoBits(ctrlMask, minNonTarg, targ); |
| 188 | } |
| 189 | |
| 190 | // swap the prefix targ with the smallest available suffix targ |
| 191 | targs[i] = minNonTarg; |
| 192 | |
| 193 | // update our targ trackers |
| 194 | targMask = flipTwoBits(targMask, targ, minNonTarg); |
| 195 | minNonTarg = getIndOfNextRightmostZeroBit(targMask, minNonTarg); |
| 196 | } |
| 197 | |
| 198 | // the ordering in ctrls relative to the caller's ctrlStates is unchanged |
| 199 | return tuple{ctrls, targs}; |
| 200 | } |
| 201 | |
| 202 | |
| 203 | auto getQubitsSwappedToMaxSuffix(Qureg qureg, vector<int> qubits) { |
no test coverage detected