Qrack  9.13
General classical-emulating-quantum development framework
qengineshard.hpp
Go to the documentation of this file.
1 //
3 // (C) Daniel Strano and the Qrack contributors 2017-2023. All rights reserved.
4 //
5 // QEngineShard is the atomic qubit unit of the QUnit mapper. "PhaseShard" optimizations are basically just a very
6 // specific "gate fusion" type optimization, where multiple gates are composed into single product gates before
7 // application to the state vector, to reduce the total number of gates that need to be applied. Rather than handling
8 // this as a "QFusion" layer optimization, which will typically sit BETWEEN a base QEngine set of "shards" and a QUnit
9 // that owns them, this particular gate fusion optimization can be avoid representational entanglement in QUnit in the
10 // first place, which QFusion would not help with. Alternatively, another QFusion would have to be in place ABOVE the
11 // QUnit layer, (with QEngine "below,") for this to work. Additionally, QFusion is designed to handle more general gate
12 // fusion, not specifically controlled phase gates, which are entirely commuting among each other and possibly a
13 // jumping-off point for further general "Fourier basis" optimizations which should probably reside in QUnit, analogous
14 // to the |+>/|-> basis changes QUnit takes advantage of for "H" gates.
15 //
16 // Licensed under the GNU Lesser General Public License V3.
17 // See LICENSE.md in the project root or https://www.gnu.org/licenses/lgpl-3.0.en.html
18 // for details.
19 
20 #pragma once
21 
22 #include "qinterface.hpp"
23 
24 #define IS_ARG_0(c) IS_SAME(c, ONE_CMPLX)
25 #define IS_ARG_PI(c) IS_OPPOSITE(c, ONE_CMPLX)
26 
27 namespace Qrack {
28 
31 struct PhaseShard {
34  bool isInvert;
35 
39  , isInvert(false)
40  {
41  }
42 };
43 
44 class QEngineShard;
46 typedef std::shared_ptr<PhaseShard> PhaseShardPtr;
47 typedef std::map<QEngineShardPtr, PhaseShardPtr> ShardToPhaseMap;
48 
50 class QEngineShard {
51 protected:
53  typedef void (QEngineShard::*OptimizeFn)();
55  typedef void (QEngineShard::*AddAnglesFn)(
56  QEngineShardPtr control, const complex& cmplxDiff, const complex& cmplxSame);
57 
58 public:
66  // Shards which this shard controls
68  // Shards which this shard (anti-)controls
70  // Shards of which this shard is a target
72  // Shards of which this shard is an (anti-controlled) target
74  // For FindShardIndex
75  bool found;
76 
77 protected:
78  // We'd rather not have these getters at all, but we need their function pointers.
83 
84 public:
86  : unit(NULL)
87  , mapped(0)
88  , isProbDirty(false)
89  , isPhaseDirty(false)
90  , amp0(ONE_CMPLX)
91  , amp1(ZERO_CMPLX)
93  , controlsShards()
95  , targetOfShards()
97  , found(false)
98  {
99  }
100 
101  QEngineShard(const bool& set, const complex& rand_phase = ONE_CMPLX)
102  : unit(NULL)
103  , mapped(0)
104  , isProbDirty(false)
105  , isPhaseDirty(false)
106  , pauliBasis(PauliZ)
107  , controlsShards()
109  , targetOfShards()
111  , found(false)
112  {
113  amp0 = set ? ZERO_CMPLX : rand_phase;
114  amp1 = set ? rand_phase : ZERO_CMPLX;
115  }
116 
117  // Dirty state constructor:
119  : unit(u)
120  , mapped(mapping)
121  , isProbDirty(true)
122  , isPhaseDirty(true)
123  , amp0(ONE_CMPLX)
124  , amp1(ZERO_CMPLX)
125  , pauliBasis(PauliZ)
126  , controlsShards()
128  , targetOfShards()
130  , found(false)
131  {
132  }
133 
134  void MakeDirty()
135  {
136  isProbDirty = true;
137  isPhaseDirty = true;
138  }
139 
140  bool ClampAmps();
141  void DumpMultiBit();
142 
143 protected:
144  void RemoveBuffer(QEngineShardPtr p, ShardToPhaseMap& localMap, GetBufferFn remoteMapGet);
145 
146 public:
150  {
152  }
154  {
156  }
157 
158 protected:
159  void DumpBuffer(OptimizeFn optimizeFn, ShardToPhaseMap& localMap, AddRemoveFn remoteFn);
160  void DumpSamePhaseBuffer(OptimizeFn optimizeFn, ShardToPhaseMap& localMap, AddRemoveFn remoteFn);
161 
162 public:
165  {
167  }
169  {
171  }
173  {
175  }
176 
177 protected:
178  void AddBuffer(QEngineShardPtr p, ShardToPhaseMap& localMap, GetBufferFn remoteFn);
179 
180 public:
184  {
186  }
188  {
190  }
191 
192 protected:
193  void AddAngles(QEngineShardPtr control, const complex& cmplxDiff, const complex& cmplxSame, AddRemoveFn localFn,
194  ShardToPhaseMap& localMap, AddRemoveFn remoteFn);
195 
196 public:
197  void AddPhaseAngles(QEngineShardPtr control, const complex& topLeft, const complex& bottomRight)
198  {
199  AddAngles(control, topLeft, bottomRight, &QEngineShard::MakePhaseControlledBy, targetOfShards,
201  }
202  void AddAntiPhaseAngles(QEngineShardPtr control, const complex& bottomRight, const complex& topLeft)
203  {
206  }
207  void AddInversionAngles(QEngineShardPtr control, const complex& topRight, const complex& bottomLeft)
208  {
209  MakePhaseControlledBy(control);
210  targetOfShards[control]->isInvert = !targetOfShards[control]->isInvert;
211  std::swap(targetOfShards[control]->cmplxDiff, targetOfShards[control]->cmplxSame);
212  AddPhaseAngles(control, topRight, bottomLeft);
213  }
214  void AddAntiInversionAngles(QEngineShardPtr control, const complex& bottomLeft, const complex& topRight)
215  {
216  MakePhaseAntiControlledBy(control);
217  antiTargetOfShards[control]->isInvert = !antiTargetOfShards[control]->isInvert;
218  std::swap(antiTargetOfShards[control]->cmplxDiff, antiTargetOfShards[control]->cmplxSame);
219  AddAntiPhaseAngles(control, bottomLeft, topRight);
220  }
221 
222 protected:
223  void OptimizeBuffer(ShardToPhaseMap& localMap, GetBufferFn remoteMapGet, AddAnglesFn phaseFn, bool makeThisControl);
224 
225 public:
227  {
229  }
231  {
233  }
235  {
238  }
240  {
243  }
244 
245  void OptimizeBothTargets();
246 
247 protected:
248  void CombineBuffers(GetBufferFn targetMapGet, GetBufferFn controlMapGet, AddAnglesFn angleFn);
249 
250 public:
253  {
258  }
259 
260  void SwapTargetAnti(QEngineShardPtr control);
261  void FlipPhaseAnti();
262  void CommutePhase(const complex& topLeft, const complex& bottomRight);
263 
264 protected:
265  void RemoveIdentityBuffers(ShardToPhaseMap& localMap, GetBufferFn remoteMapGet);
266  void RemovePhaseBuffers(ShardToPhaseMap& localMap, GetBufferFn remoteMapGet);
267 
268 public:
269  void CommuteH();
270 
272  {
277  }
278 
279  bool IsInvertControl();
280  bool IsInvertTarget();
281 
282 protected:
284 
285 public:
287  {
288  // Upon measurement, buffered phase can sometimes be totally ignored.
289  // If we clear phase before applying buffered inversions, we can optimize application as CNOT.
294  }
295 
296  bitLenInt GetQubitCount() { return unit ? unit->GetQubitCount() : 1U; };
298  {
299  if (!isProbDirty || !unit) {
300  return norm(amp1);
301  }
302 
303  return unit->Prob(mapped);
304  }
305  bool isClifford()
306  {
307  return (unit && unit->isClifford(mapped)) ||
308  (!unit &&
309  ((norm(amp0) <= FP_NORM_EPSILON) || (norm(amp1) <= FP_NORM_EPSILON) ||
310  (norm(amp0 - amp1) <= FP_NORM_EPSILON) || (norm(amp0 + amp1) <= FP_NORM_EPSILON) ||
311  (norm(amp0 - I_CMPLX * amp1) <= FP_NORM_EPSILON) ||
312  (norm(amp0 + I_CMPLX * amp1) <= FP_NORM_EPSILON)));
313  };
314 };
315 
317 protected:
318  std::vector<QEngineShard> shards;
319  std::vector<bitLenInt> swapMap;
320 
321 public:
323  {
324  // Intentionally left blank
325  }
326 
328  : shards(size)
329  , swapMap(size)
330  {
331  for (bitLenInt i = 0U; i < size; ++i) {
332  swapMap[i] = i;
333  }
334  }
335 
336  typedef std::vector<QEngineShard>::iterator iterator;
337 
338  QEngineShard& operator[](const bitLenInt& i) { return shards[swapMap[i]]; }
339 
340  iterator begin() { return shards.begin(); }
341 
342  iterator end() { return shards.end(); }
343 
344  bitLenInt size() { return shards.size(); }
345 
346  void push_back(const QEngineShard& shard)
347  {
348  shards.push_back(shard);
349  swapMap.push_back(swapMap.size());
350  }
351 
352  void insert(bitLenInt start, QEngineShardMap& toInsert)
353  {
354  bitLenInt oSize = size();
355 
356  shards.insert(shards.end(), toInsert.shards.begin(), toInsert.shards.end());
357  swapMap.insert(swapMap.begin() + start, toInsert.swapMap.begin(), toInsert.swapMap.end());
358 
359  for (bitLenInt lcv = 0U; lcv < toInsert.size(); ++lcv) {
360  swapMap[(size_t)start + lcv] += oSize;
361  }
362  }
363 
365  {
366  for (bitLenInt index = begin; index < end; ++index) {
367  bitLenInt offset = swapMap[index];
368  shards.erase(shards.begin() + offset);
369 
370  for (bitLenInt lcv = 0U; lcv < (bitLenInt)swapMap.size(); ++lcv) {
371  if (swapMap[lcv] >= offset) {
372  --(swapMap[lcv]);
373  }
374  }
375  }
376 
377  swapMap.erase(swapMap.begin() + begin, swapMap.begin() + end);
378  }
379 
380  void swap(bitLenInt qubit1, bitLenInt qubit2) { std::swap(swapMap[qubit1], swapMap[qubit2]); }
381 
382  void reindex()
383  {
384  std::map<QInterfacePtr, bitLenInt> indices;
385  for (auto&& shard : shards) {
386  if (!shard.unit) {
387  shard.mapped = 0U;
388  continue;
389  }
390  shard.mapped = indices[shard.unit]++;
391  }
392  for (size_t i = 0U; i < shards.size(); ++i) {
393  swapMap[i] = i;
394  }
395  }
396 };
397 } // namespace Qrack
Definition: qengineshard.hpp:316
std::vector< bitLenInt > swapMap
Definition: qengineshard.hpp:319
std::vector< QEngineShard >::iterator iterator
Definition: qengineshard.hpp:336
std::vector< QEngineShard > shards
Definition: qengineshard.hpp:318
void push_back(const QEngineShard &shard)
Definition: qengineshard.hpp:346
bitLenInt size()
Definition: qengineshard.hpp:344
QEngineShardMap()
Definition: qengineshard.hpp:322
QEngineShardMap(const bitLenInt &size)
Definition: qengineshard.hpp:327
void swap(bitLenInt qubit1, bitLenInt qubit2)
Definition: qengineshard.hpp:380
void erase(bitLenInt begin, bitLenInt end)
Definition: qengineshard.hpp:364
void insert(bitLenInt start, QEngineShardMap &toInsert)
Definition: qengineshard.hpp:352
iterator begin()
Definition: qengineshard.hpp:340
iterator end()
Definition: qengineshard.hpp:342
void reindex()
Definition: qengineshard.hpp:382
QEngineShard & operator[](const bitLenInt &i)
Definition: qengineshard.hpp:338
Associates a QInterface object with a set of bits.
Definition: qengineshard.hpp:50
void CombineGates()
If this bit is both control and target of another bit, try to combine the operations into one gate.
Definition: qengineshard.hpp:252
void AddBuffer(QEngineShardPtr p, ShardToPhaseMap &localMap, GetBufferFn remoteFn)
Definition: qengineshard.cpp:110
void OptimizeBothTargets()
Definition: qengineshard.cpp:165
void AddAntiInversionAngles(QEngineShardPtr control, const complex &bottomLeft, const complex &topRight)
Definition: qengineshard.hpp:214
void AddAngles(QEngineShardPtr control, const complex &cmplxDiff, const complex &cmplxSame, AddRemoveFn localFn, ShardToPhaseMap &localMap, AddRemoveFn remoteFn)
Definition: qengineshard.cpp:119
void DumpControlOf()
Definition: qengineshard.hpp:163
QEngineShard(QInterfacePtr u, const bitLenInt &mapping)
Definition: qengineshard.hpp:118
ShardToPhaseMap & GetAntiControlsShards()
Definition: qengineshard.hpp:80
void DumpMultiBit()
Definition: qengineshard.cpp:48
void MakePhaseControlledBy(QEngineShardPtr p)
Definition: qengineshard.hpp:181
void AddPhaseAngles(QEngineShardPtr control, const complex &topLeft, const complex &bottomRight)
Definition: qengineshard.hpp:197
complex amp0
Definition: qengineshard.hpp:63
ShardToPhaseMap & GetControlsShards()
Definition: qengineshard.hpp:79
void FlipPhaseAnti()
Definition: qengineshard.cpp:255
void RemoveIdentityBuffers(ShardToPhaseMap &localMap, GetBufferFn remoteMapGet)
Definition: qengineshard.cpp:301
void OptimizeAntiTargets()
Definition: qengineshard.hpp:239
bool ClampAmps()
Definition: qengineshard.cpp:26
bitLenInt mapped
Definition: qengineshard.hpp:60
void(QEngineShard::* OptimizeFn)()
Definition: qengineshard.hpp:53
void OptimizeAntiControls()
Definition: qengineshard.hpp:234
ShardToPhaseMap antiTargetOfShards
Definition: qengineshard.hpp:73
void RemovePhaseBuffers(ShardToPhaseMap &localMap, GetBufferFn remoteMapGet)
Definition: qengineshard.cpp:321
void CommutePhase(const complex &topLeft, const complex &bottomRight)
Definition: qengineshard.cpp:278
bool isProbDirty
Definition: qengineshard.hpp:61
ShardToPhaseMap targetOfShards
Definition: qengineshard.hpp:71
void RemoveControl(QEngineShardPtr p)
Definition: qengineshard.hpp:147
bitLenInt GetQubitCount()
Definition: qengineshard.hpp:296
void DumpAntiControlOf()
Definition: qengineshard.hpp:164
bool isClifford()
Definition: qengineshard.hpp:305
QEngineShard()
Definition: qengineshard.hpp:85
QInterfacePtr unit
Definition: qengineshard.hpp:59
void MakePhaseAntiControlledBy(QEngineShardPtr p)
Definition: qengineshard.hpp:183
void RemoveTarget(QEngineShardPtr p)
Definition: qengineshard.hpp:148
void RemoveAntiTarget(QEngineShardPtr p)
Definition: qengineshard.hpp:153
QEngineShard(const bool &set, const complex &rand_phase=ONE_CMPLX)
Definition: qengineshard.hpp:101
void RemoveBuffer(QEngineShardPtr p, ShardToPhaseMap &localMap, GetBufferFn remoteMapGet)
Definition: qengineshard.cpp:72
void MakePhaseAntiControlOf(QEngineShardPtr p)
Definition: qengineshard.hpp:187
ShardToPhaseMap & GetAntiTargetOfShards()
Definition: qengineshard.hpp:82
void OptimizeBuffer(ShardToPhaseMap &localMap, GetBufferFn remoteMapGet, AddAnglesFn phaseFn, bool makeThisControl)
Definition: qengineshard.cpp:141
void AddAntiPhaseAngles(QEngineShardPtr control, const complex &bottomRight, const complex &topLeft)
Definition: qengineshard.hpp:202
void ClearInvertPhase()
Definition: qengineshard.hpp:286
real1_f Prob()
Definition: qengineshard.hpp:297
void AddInversionAngles(QEngineShardPtr control, const complex &topRight, const complex &bottomLeft)
Definition: qengineshard.hpp:207
ShardToPhaseMap & GetTargetOfShards()
Definition: qengineshard.hpp:81
void DumpPhaseBuffers()
Definition: qengineshard.hpp:271
ShardToPhaseMap controlsShards
Definition: qengineshard.hpp:67
Pauli pauliBasis
Definition: qengineshard.hpp:65
void DumpBuffer(OptimizeFn optimizeFn, ShardToPhaseMap &localMap, AddRemoveFn remoteFn)
Definition: qengineshard.cpp:81
ShardToPhaseMap &(QEngineShard::* GetBufferFn)()
Definition: qengineshard.hpp:52
void(QEngineShard::* AddRemoveFn)(QEngineShardPtr)
Definition: qengineshard.hpp:54
void MakePhaseControlOf(QEngineShardPtr p)
Definition: qengineshard.hpp:182
void SwapTargetAnti(QEngineShardPtr control)
Definition: qengineshard.cpp:236
void OptimizeTargets()
Definition: qengineshard.hpp:230
complex amp1
Definition: qengineshard.hpp:64
void DumpSamePhaseAntiControlOf()
Definition: qengineshard.hpp:172
bool found
Definition: qengineshard.hpp:75
void MakeDirty()
Definition: qengineshard.hpp:134
bool IsInvertTarget()
Definition: qengineshard.cpp:399
void RemoveAntiControl(QEngineShardPtr p)
Definition: qengineshard.hpp:149
void DumpSamePhaseControlOf()
Definition: qengineshard.hpp:168
ShardToPhaseMap antiControlsShards
Definition: qengineshard.hpp:69
bool IsInvertControl()
Definition: qengineshard.cpp:382
void(QEngineShard::* AddAnglesFn)(QEngineShardPtr control, const complex &cmplxDiff, const complex &cmplxSame)
Definition: qengineshard.hpp:55
void ClearMapInvertPhase(ShardToPhaseMap &shards)
Definition: qengineshard.cpp:416
bool isPhaseDirty
Definition: qengineshard.hpp:62
void DumpSamePhaseBuffer(OptimizeFn optimizeFn, ShardToPhaseMap &localMap, AddRemoveFn remoteFn)
Definition: qengineshard.cpp:91
void CombineBuffers(GetBufferFn targetMapGet, GetBufferFn controlMapGet, AddAnglesFn angleFn)
Definition: qengineshard.cpp:208
void CommuteH()
Definition: qengineshard.cpp:340
void OptimizeControls()
Definition: qengineshard.hpp:226
GLOSSARY: bitLenInt - "bit-length integer" - unsigned integer ID of qubit position in register bitCap...
Definition: complex16x2simd.hpp:25
std::shared_ptr< QInterface > QInterfacePtr
Definition: qinterface.hpp:29
std::shared_ptr< PhaseShard > PhaseShardPtr
Definition: qengineshard.hpp:46
void U(quid sid, bitLenInt q, real1_f theta, real1_f phi, real1_f lambda)
(External API) 3-parameter unitary gate
Definition: wasm_api.cpp:1143
std::complex< real1 > complex
Definition: qrack_types.hpp:128
QRACK_CONST real1 FP_NORM_EPSILON
Definition: qrack_types.hpp:258
double norm(const complex2 &c)
Definition: complex16x2simd.hpp:101
QRACK_CONST complex ONE_CMPLX
Definition: qrack_types.hpp:252
float real1_f
Definition: qrack_types.hpp:95
QRACK_CONST complex I_CMPLX
Definition: qrack_types.hpp:254
std::map< QEngineShardPtr, PhaseShardPtr > ShardToPhaseMap
Definition: qengineshard.hpp:47
Pauli
Enumerated list of Pauli bases.
Definition: pauli.hpp:19
@ PauliZ
Pauli Z operator. Corresponds to Q# constant "PauliZ.".
Definition: pauli.hpp:27
QRACK_CONST complex ZERO_CMPLX
Definition: qrack_types.hpp:253
std::map< QInterface *, std::map< quid, bitLenInt > > shards
Definition: wasm_api.cpp:240
QEngineShard * QEngineShardPtr
Definition: qengineshard.hpp:44
#define bitLenInt
Definition: qrack_types.hpp:38
Caches controlled gate phase between shards, (as a case of "gate fusion" optimization particularly us...
Definition: qengineshard.hpp:31
complex cmplxSame
Definition: qengineshard.hpp:33
PhaseShard()
Definition: qengineshard.hpp:36
bool isInvert
Definition: qengineshard.hpp:34
complex cmplxDiff
Definition: qengineshard.hpp:32