Quantum++  v1.1
A modern C++11 quantum computing library
reversible.h
Go to the documentation of this file.
1 /*
2  * This file is part of Quantum++.
3  *
4  * MIT License
5  *
6  * Copyright (c) 2013 - 2019 Vlad Gheorghiu (vgheorgh@gmail.com)
7  *
8  * Permission is hereby granted, free of charge, to any person obtaining a copy
9  * of this software and associated documentation files (the "Software"), to deal
10  * in the Software without restriction, including without limitation the rights
11  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12  * copies of the Software, and to permit persons to whom the Software is
13  * furnished to do so, subject to the following conditions:
14  *
15  * The above copyright notice and this permission notice shall be included in
16  * all copies or substantial portions of the Software.
17  *
18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24  * SOFTWARE.
25  */
26 
32 #ifndef CLASSES_REVERSIBLE_H
33 #define CLASSES_REVERSIBLE_H
34 
35 namespace qpp {
41 class Dynamic_bitset : public IDisplay {
42  public:
43  using value_type = unsigned int;
44  using storage_type = std::vector<value_type>;
45  protected:
47  idx N_;
48  std::vector<value_type> v_;
49 
56  idx index_(idx pos) const { return pos / (sizeof(value_type) * CHAR_BIT); }
57 
65  idx offset_(idx pos) const { return pos % (sizeof(value_type) * CHAR_BIT); }
66 
67  public:
74  : storage_size_{N / (sizeof(value_type) * CHAR_BIT) + 1}, N_{N},
75  v_(storage_size_) {}
76 
77  /* getters */
78 
84  const storage_type& data() const { return v_; }
85 
91  idx size() const noexcept { return N_; }
92 
99  idx storage_size() const noexcept { return storage_size_; }
100 
106  idx count() const noexcept {
107  idx result = 0;
108  idx bitset_size = this->size();
109  for (idx i = 0; i < bitset_size; ++i) {
110  if (this->get(i))
111  ++result;
112  }
113 
114  return result;
115  }
116 
123  bool get(idx pos) const noexcept {
124  return 1 & (v_[index_(pos)] >> offset_(pos));
125  }
126 
132  bool none() const noexcept {
133  bool result = true;
134  idx bitset_storage_size = this->storage_size();
135  for (idx i = 0; i < bitset_storage_size; ++i) {
136  if (v_[i]) {
137  return false;
138  }
139  }
140 
141  return result;
142  }
143 
149  bool all() const noexcept {
150  bool result = true;
151  idx bitset_storage_size = this->storage_size();
152  for (idx i = 0; i < bitset_storage_size; ++i) {
153  if (~v_[i]) {
154  return false;
155  }
156  }
157 
158  return result;
159  }
160 
166  bool any() const noexcept { return !(this->none()); }
167 
168  /* setters */
176  Dynamic_bitset& set(idx pos, bool value = true) {
177  value ? v_[index_(pos)] |= (1 << offset_(pos))
178  : v_[index_(pos)] &= ~(1 << offset_(pos));
179 
180  // v_[index_(pos)] &= ~(!value << offset_(pos));
181 
182  return *this;
183  }
184 
190  Dynamic_bitset& set() noexcept {
191  idx bitset_storage_size = this->storage_size();
192  for (idx i = 0; i < bitset_storage_size; ++i) {
193  v_[i] = ~0;
194  }
195 
196  return *this;
197  }
198 
207  Dynamic_bitset& rand(idx pos, double p = 0.5) {
208  std::random_device rd;
209  std::mt19937 gen{rd()};
210  std::bernoulli_distribution d{p};
211 
212  this->set(pos, d(gen));
213 
214  return *this;
215  }
216 
223  Dynamic_bitset& rand(double p = 0.5) {
224  idx bitset_size = this->size();
225  for (idx i = 0; i < bitset_size; ++i) {
226  this->rand(i, p);
227  }
228 
229  return *this;
230  }
231 
239  v_[index_(pos)] &= ~(1 << offset_(pos));
240 
241  return *this;
242  }
243 
249  Dynamic_bitset& reset() noexcept {
250  idx bitset_storage_size = this->storage_size();
251  for (idx i = 0; i < bitset_storage_size; ++i) {
252  v_[i] = 0;
253  }
254 
255  return *this;
256  }
257 
265  v_[index_(pos)] ^= 1 << (offset_(pos));
266 
267  return *this;
268  }
269 
275  Dynamic_bitset& flip() noexcept {
276  idx bitset_storage_size = this->storage_size();
277  for (idx i = 0; i < bitset_storage_size; ++i) {
278  v_[i] = ~v_[i];
279  }
280 
281  return *this;
282  }
283 
284  /* operators */
291  bool operator==(const Dynamic_bitset& rhs) const noexcept {
292  assert(this->size() == rhs.size());
293  bool result = true;
294  idx n = std::min(this->storage_size(), rhs.storage_size());
295  for (idx i = 0; i < n; ++i) {
296  if (v_[i] != rhs.v_[i]) {
297  return false;
298  }
299  }
300 
301  return result;
302  }
303 
310  bool operator!=(const Dynamic_bitset& rhs) const noexcept {
311  return !(*this == rhs);
312  }
313 
321  idx operator-(const Dynamic_bitset& rhs) const noexcept {
322  idx result = 0;
323  idx bitset_size = this->size();
324  for (idx i = 0; i < bitset_size; ++i) {
325  if (this->get(i) != rhs.get(i))
326  ++result;
327  }
328 
329  return result;
330  }
331 
332  /* input/output */
343  template <class CharT = char, class Traits = std::char_traits<CharT>,
344  class Allocator = std::allocator<CharT>>
345  std::basic_string<CharT, Traits, Allocator>
346  to_string(CharT zero = CharT('0'), CharT one = CharT('1')) const {
347  std::basic_string<CharT, Traits, Allocator> result;
348  idx bitset_size = this->size();
349  result.resize(bitset_size);
350 
351  for (idx i = bitset_size; i-- > 0;) {
352  if (!this->get(i)) {
353  result[bitset_size - i - 1] = zero;
354  } else {
355  result[bitset_size - i - 1] = one;
356  }
357  }
358 
359  return result;
360  }
361 
362  private:
369  std::ostream& display(std::ostream& os) const override {
370  idx bitset_size = this->size();
371  for (idx i = bitset_size; i-- > 0;) {
372  os << this->get(i);
373  }
374 
375  return os;
376  }
377 }; /* class Dynamic_bitset */
378 
383 class Bit_circuit : public Dynamic_bitset {
384  public:
385  struct Gate_count {
386  // 1 bit gates
387  idx NOT = 0;
388  idx& X = NOT;
389 
390  // 2 bit gates
391  idx CNOT = 0;
392  idx SWAP = 0;
393 
394  // 3 bit gates
395  idx FRED = 0;
396  idx TOF = 0;
397  } gate_count{};
398 
403 
410  Bit_circuit(const Dynamic_bitset& dynamic_bitset)
411  : Dynamic_bitset{dynamic_bitset} {};
412 
420  Bit_circuit& X(idx pos) {
421  this->flip(pos);
422  ++gate_count.X;
423 
424  return *this;
425  }
426 
435  this->flip(pos);
436  ++gate_count.NOT;
437 
438  return *this;
439  }
440 
447  Bit_circuit& CNOT(const std::vector<idx>& pos) {
448  v_[index_(pos[1])] ^= (1 & (v_[index_(pos[0])] >> offset_(pos[0])))
449  << offset_(pos[1]);
450  ++gate_count.CNOT;
451 
452  return *this;
453  }
454 
462  Bit_circuit& TOF(const std::vector<idx>& pos) {
463  v_[index_(pos[2])] ^= ((1 & (v_[index_(pos[1])] >> offset_(pos[1]))) &
464  (1 & (v_[index_(pos[0])] >> offset_(pos[0]))))
465  << offset_(pos[2]);
466  ++gate_count.TOF;
467 
468  return *this;
469  }
470 
477  Bit_circuit& SWAP(const std::vector<idx>& pos) {
478  if (this->get(pos[0]) != this->get(pos[1])) {
479  this->X(pos[0]);
480  this->X(pos[1]);
481  }
482  ++gate_count.SWAP;
483 
484  return *this;
485  }
486 
494  Bit_circuit& FRED(const std::vector<idx>& pos) {
495  if (this->get(pos[0])) {
496  this->SWAP({pos[1], pos[2]});
497  }
498  ++gate_count.FRED;
499 
500  return *this;
501  }
502 
508  Bit_circuit& reset() noexcept {
509  gate_count.NOT = gate_count.X = 0;
510  gate_count.CNOT = gate_count.SWAP = 0;
511  gate_count.FRED = gate_count.TOF = 0;
513 
514  return *this;
515  }
516 }; /* class Bit_circuit */
517 
518 } /* namespace qpp */
519 
520 #endif /* CLASSES_REVERSIBLE_H */
unsigned int value_type
Type of the storage elements.
Definition: reversible.h:43
Bit_circuit & TOF(const std::vector< idx > &pos)
Toffoli gate.
Definition: reversible.h:462
idx storage_size() const noexcept
Size of the underlying storage space (in units of value_type, unsigned int by default) ...
Definition: reversible.h:99
idx index_(idx pos) const
Index of the pos bit in the storage space.
Definition: reversible.h:56
const storage_type & data() const
Raw storage space of the bitset.
Definition: reversible.h:84
Quantum++ main namespace.
Definition: codes.h:35
Definition: reversible.h:385
bool operator==(const Dynamic_bitset &rhs) const noexcept
Equality operator.
Definition: reversible.h:291
Bit_circuit & reset() noexcept
Reset the circuit all zero, clear all gates.
Definition: reversible.h:508
std::vector< value_type > storage_type
Type of the storage.
Definition: reversible.h:44
Bit_circuit & NOT(idx pos)
Bit flip.
Definition: reversible.h:434
bool any() const noexcept
Checks whether any bit is set.
Definition: reversible.h:166
idx N_
Number of bits.
Definition: reversible.h:47
idx storage_size_
Storage size.
Definition: reversible.h:46
bool all() const noexcept
Checks whether all bits are set.
Definition: reversible.h:149
Bit_circuit & SWAP(const std::vector< idx > &pos)
Swap bits.
Definition: reversible.h:477
idx operator-(const Dynamic_bitset &rhs) const noexcept
Number of places the two bitsets differ (Hamming distance)
Definition: reversible.h:321
Dynamic bitset class, allows the specification of the number of bits at runtime (unlike std::bitset<N...
Definition: reversible.h:41
Abstract class (interface) that mandates the definition of virtual std::ostream& display(std::ostream...
Definition: idisplay.h:46
idx count() const noexcept
Number of bits set to one in the bitset (Hamming weight)
Definition: reversible.h:106
std::ostream & display(std::ostream &os) const override
qpp::IDisplay::display() override, displays the bitset bit by bit
Definition: reversible.h:369
Bit_circuit & X(idx pos)
Bit flip.
Definition: reversible.h:420
idx size() const noexcept
Number of bits stored in the bitset.
Definition: reversible.h:91
Bit_circuit & CNOT(const std::vector< idx > &pos)
Controlled-NOT.
Definition: reversible.h:447
std::basic_string< CharT, Traits, Allocator > to_string(CharT zero=CharT('0'), CharT one=CharT('1')) const
String representation.
Definition: reversible.h:346
Classical reversible circuit simulator.
Definition: reversible.h:383
Dynamic_bitset & flip() noexcept
Flips all bits.
Definition: reversible.h:275
Dynamic_bitset(idx N)
Constructor, initializes all bits to false (zero)
Definition: reversible.h:73
bool none() const noexcept
Checks whether none of the bits are set.
Definition: reversible.h:132
std::vector< value_type > v_
Storage space.
Definition: reversible.h:48
Dynamic_bitset & reset(idx pos)
Sets the bit at position pos to false.
Definition: reversible.h:238
Bit_circuit & FRED(const std::vector< idx > &pos)
Fredkin gate (Controlled-SWAP)
Definition: reversible.h:494
std::size_t idx
Non-negative integer index.
Definition: types.h:39
bool operator!=(const Dynamic_bitset &rhs) const noexcept
Inequality operator.
Definition: reversible.h:310
Bit_circuit(const Dynamic_bitset &dynamic_bitset)
Conversion constructor, used to initialize a qpp::Bit_circuit with a qpp::Dynamic_bitset.
Definition: reversible.h:410
Dynamic_bitset & reset() noexcept
Sets all bits to false.
Definition: reversible.h:249
Dynamic_bitset & flip(idx pos)
Flips the bit at position pos.
Definition: reversible.h:264
Dynamic_bitset & rand(idx pos, double p=0.5)
Sets the bit at position pos according to a Bernoulli(p) distribution.
Definition: reversible.h:207
Dynamic_bitset & rand(double p=0.5)
Sets all bits according to a Bernoulli(p) distribution.
Definition: reversible.h:223
idx offset_(idx pos) const
Offset of the pos bit in the storage space relative to its index.
Definition: reversible.h:65