Quantum++  v1.2
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 
66  idx offset_(idx pos) const { return pos % (sizeof(value_type) * CHAR_BIT); }
67 
68  public:
74  explicit Dynamic_bitset(idx N)
75  : storage_size_{N / (sizeof(value_type) * CHAR_BIT) + 1}, N_{N},
76  v_(storage_size_) {}
77 
81  virtual ~Dynamic_bitset() = default;
82 
83  /* getters */
84 
90  const storage_type& data() const { return v_; }
91 
97  idx size() const noexcept { return N_; }
98 
105  idx storage_size() const noexcept { return storage_size_; }
106 
112  idx count() const noexcept {
113  idx result = 0;
114  idx bitset_size = this->size();
115  for (idx i = 0; i < bitset_size; ++i) {
116  if (this->get(i))
117  ++result;
118  }
119 
120  return result;
121  }
122 
129  bool get(idx pos) const noexcept {
130  return 1 & (v_[index_(pos)] >> offset_(pos));
131  }
132 
138  bool none() const noexcept {
139  bool result = true;
140  idx bitset_storage_size = this->storage_size();
141  for (idx i = 0; i < bitset_storage_size; ++i) {
142  if (v_[i]) {
143  return false;
144  }
145  }
146 
147  return result;
148  }
149 
155  bool all() const noexcept {
156  bool result = true;
157  idx bitset_storage_size = this->storage_size();
158  for (idx i = 0; i < bitset_storage_size; ++i) {
159  if (~v_[i]) {
160  return false;
161  }
162  }
163 
164  return result;
165  }
166 
172  bool any() const noexcept { return !(this->none()); }
173 
174  /* setters */
182  Dynamic_bitset& set(idx pos, bool value = true) {
183  value ? v_[index_(pos)] |= (1 << offset_(pos))
184  : v_[index_(pos)] &= ~(1 << offset_(pos));
185 
186  // v_[index_(pos)] &= ~(!value << offset_(pos));
187 
188  return *this;
189  }
190 
196  Dynamic_bitset& set() noexcept {
197  idx bitset_storage_size = this->storage_size();
198  for (idx i = 0; i < bitset_storage_size; ++i) {
199  v_[i] = ~0;
200  }
201 
202  return *this;
203  }
204 
213  Dynamic_bitset& rand(idx pos, double p = 0.5) {
214  std::random_device rd;
215  std::mt19937 gen{rd()};
216  std::bernoulli_distribution d{p};
217 
218  this->set(pos, d(gen));
219 
220  return *this;
221  }
222 
229  Dynamic_bitset& rand(double p = 0.5) {
230  idx bitset_size = this->size();
231  for (idx i = 0; i < bitset_size; ++i) {
232  this->rand(i, p);
233  }
234 
235  return *this;
236  }
237 
245  v_[index_(pos)] &= ~(1 << offset_(pos));
246 
247  return *this;
248  }
249 
255  Dynamic_bitset& reset() noexcept {
256  idx bitset_storage_size = this->storage_size();
257  for (idx i = 0; i < bitset_storage_size; ++i) {
258  v_[i] = 0;
259  }
260 
261  return *this;
262  }
263 
271  v_[index_(pos)] ^= 1 << (offset_(pos));
272 
273  return *this;
274  }
275 
281  Dynamic_bitset& flip() noexcept {
282  idx bitset_storage_size = this->storage_size();
283  for (idx i = 0; i < bitset_storage_size; ++i) {
284  v_[i] = ~v_[i];
285  }
286 
287  return *this;
288  }
289 
290  /* operators */
297  bool operator==(const Dynamic_bitset& rhs) const noexcept {
298  assert(this->size() == rhs.size());
299  bool result = true;
300  idx n = std::min(this->storage_size(), rhs.storage_size());
301  for (idx i = 0; i < n; ++i) {
302  if (v_[i] != rhs.v_[i]) {
303  return false;
304  }
305  }
306 
307  return result;
308  }
309 
316  bool operator!=(const Dynamic_bitset& rhs) const noexcept {
317  return !(*this == rhs);
318  }
319 
327  idx operator-(const Dynamic_bitset& rhs) const noexcept {
328  idx result = 0;
329  idx bitset_size = this->size();
330  for (idx i = 0; i < bitset_size; ++i) {
331  if (this->get(i) != rhs.get(i))
332  ++result;
333  }
334 
335  return result;
336  }
337 
338  /* input/output */
349  template <class CharT = char, class Traits = std::char_traits<CharT>,
350  class Allocator = std::allocator<CharT>>
351  std::basic_string<CharT, Traits, Allocator>
352  to_string(CharT zero = CharT('0'), CharT one = CharT('1')) const {
353  std::basic_string<CharT, Traits, Allocator> result;
354  idx bitset_size = this->size();
355  result.resize(bitset_size);
356 
357  for (idx i = bitset_size; i-- > 0;) {
358  if (!this->get(i)) {
359  result[bitset_size - i - 1] = zero;
360  } else {
361  result[bitset_size - i - 1] = one;
362  }
363  }
364 
365  return result;
366  }
367 
368  private:
375  std::ostream& display(std::ostream& os) const override {
376  idx bitset_size = this->size();
377  for (idx i = bitset_size; i-- > 0;) {
378  os << this->get(i);
379  }
380 
381  return os;
382  }
383 }; /* class Dynamic_bitset */
384 
389 class Bit_circuit : public Dynamic_bitset {
390  public:
391  struct Gate_count {
392  // 1 bit gates
393  idx NOT = 0;
394  idx& X = NOT;
395 
396  // 2 bit gates
397  idx CNOT = 0;
398  idx SWAP = 0;
399 
400  // 3 bit gates
401  idx FRED = 0;
402  idx TOF = 0;
403  } gate_count{};
404 
409 
416  explicit Bit_circuit(const Dynamic_bitset& dynamic_bitset)
417  : Dynamic_bitset{dynamic_bitset} {};
418 
426  Bit_circuit& X(idx pos) {
427  this->flip(pos);
428  ++gate_count.X;
429 
430  return *this;
431  }
432 
441  this->flip(pos);
442  ++gate_count.NOT;
443 
444  return *this;
445  }
446 
453  Bit_circuit& CNOT(const std::vector<idx>& pos) {
454  v_[index_(pos[1])] ^= (1 & (v_[index_(pos[0])] >> offset_(pos[0])))
455  << offset_(pos[1]);
456  ++gate_count.CNOT;
457 
458  return *this;
459  }
460 
468  Bit_circuit& TOF(const std::vector<idx>& pos) {
469  v_[index_(pos[2])] ^= ((1 & (v_[index_(pos[1])] >> offset_(pos[1]))) &
470  (1 & (v_[index_(pos[0])] >> offset_(pos[0]))))
471  << offset_(pos[2]);
472  ++gate_count.TOF;
473 
474  return *this;
475  }
476 
483  Bit_circuit& SWAP(const std::vector<idx>& pos) {
484  if (this->get(pos[0]) != this->get(pos[1])) {
485  this->X(pos[0]);
486  this->X(pos[1]);
487  }
488  ++gate_count.SWAP;
489 
490  return *this;
491  }
492 
500  Bit_circuit& FRED(const std::vector<idx>& pos) {
501  if (this->get(pos[0])) {
502  this->SWAP({pos[1], pos[2]});
503  }
504  ++gate_count.FRED;
505 
506  return *this;
507  }
508 
514  Bit_circuit& reset() noexcept {
515  gate_count.NOT = gate_count.X = 0;
519 
520  return *this;
521  }
522 }; /* class Bit_circuit */
523 
524 } /* namespace qpp */
525 
526 #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:468
idx storage_size() const noexcept
Size of the underlying storage space (in units of value_type, unsigned int by default) ...
Definition: reversible.h:105
idx index_(idx pos) const
Index of the pos bit in the storage space.
Definition: reversible.h:56
idx SWAP
Definition: reversible.h:398
idx & X
Definition: reversible.h:394
const storage_type & data() const
Raw storage space of the bitset.
Definition: reversible.h:90
Quantum++ main namespace.
Definition: circuits.h:35
Definition: reversible.h:391
bool operator==(const Dynamic_bitset &rhs) const noexcept
Equality operator.
Definition: reversible.h:297
idx TOF
Definition: reversible.h:402
Bit_circuit & reset() noexcept
Reset the circuit all zero, clear all gates.
Definition: reversible.h:514
std::vector< value_type > storage_type
Type of the storage.
Definition: reversible.h:44
Bit_circuit & NOT(idx pos)
Bit flip.
Definition: reversible.h:440
idx FRED
Definition: reversible.h:401
bool any() const noexcept
Checks whether any bit is set.
Definition: reversible.h:172
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:155
virtual ~Dynamic_bitset()=default
Default virtual destructor.
struct qpp::Bit_circuit::Gate_count gate_count
Gate counters.
Bit_circuit & SWAP(const std::vector< idx > &pos)
Swap bits.
Definition: reversible.h:483
idx operator-(const Dynamic_bitset &rhs) const noexcept
Number of places the two bitsets differ (Hamming distance)
Definition: reversible.h:327
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:47
idx count() const noexcept
Number of bits set to one in the bitset (Hamming weight)
Definition: reversible.h:112
std::ostream & display(std::ostream &os) const override
qpp::IDisplay::display() override, displays the bitset bit by bit
Definition: reversible.h:375
Bit_circuit & X(idx pos)
Bit flip.
Definition: reversible.h:426
idx size() const noexcept
Number of bits stored in the bitset.
Definition: reversible.h:97
Bit_circuit & CNOT(const std::vector< idx > &pos)
Controlled-NOT.
Definition: reversible.h:453
std::basic_string< CharT, Traits, Allocator > to_string(CharT zero=CharT('0'), CharT one=CharT('1')) const
String representation.
Definition: reversible.h:352
Classical reversible circuit simulator.
Definition: reversible.h:389
Dynamic_bitset & flip() noexcept
Flips all bits.
Definition: reversible.h:281
idx CNOT
Definition: reversible.h:397
Dynamic_bitset(idx N)
Constructor, initializes all bits to false (zero)
Definition: reversible.h:74
idx NOT
Definition: reversible.h:393
bool none() const noexcept
Checks whether none of the bits are set.
Definition: reversible.h:138
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:244
Bit_circuit & FRED(const std::vector< idx > &pos)
Fredkin gate (Controlled-SWAP)
Definition: reversible.h:500
std::size_t idx
Non-negative integer index, make sure you use an unsigned type.
Definition: types.h:39
bool operator!=(const Dynamic_bitset &rhs) const noexcept
Inequality operator.
Definition: reversible.h:316
Bit_circuit(const Dynamic_bitset &dynamic_bitset)
Conversion constructor, used to initialize a qpp::Bit_circuit with a qpp::Dynamic_bitset.
Definition: reversible.h:416
Dynamic_bitset & reset() noexcept
Sets all bits to false.
Definition: reversible.h:255
Dynamic_bitset & flip(idx pos)
Flips the bit at position pos.
Definition: reversible.h:270
Dynamic_bitset & rand(idx pos, double p=0.5)
Sets the bit at position pos according to a Bernoulli(p) distribution.
Definition: reversible.h:213
Dynamic_bitset & rand(double p=0.5)
Sets all bits according to a Bernoulli(p) distribution.
Definition: reversible.h:229
idx offset_(idx pos) const
Offset of the pos bit in the storage space relative to its index.
Definition: reversible.h:66