Quantum++  v1.0-rc4
A modern C++11 quantum computing library
experimental.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 - 2018 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 EXPERIMENTAL_EXPERIMENTAL_H_
33 #define EXPERIMENTAL_EXPERIMENTAL_H_
34 
35 #include <algorithm>
36 #include <cassert>
37 #include <climits>
38 #include <cstddef>
39 #include <random>
40 #include <utility>
41 #include <vector>
42 
43 using idx = std::size_t;
44 
45 namespace qpp {
50 namespace experimental {
57  public:
58  using value_type = unsigned int;
59  using storage_type = std::vector<value_type>;
60  protected:
62  idx N_;
63  std::vector<value_type> v_;
64 
70  idx index_(idx pos) const { return pos / (sizeof(value_type) * CHAR_BIT); }
71 
78  idx offset_(idx pos) const { return pos % (sizeof(value_type) * CHAR_BIT); }
79 
80  public:
86  : storage_size_{N / (sizeof(value_type) * CHAR_BIT) + 1}, N_{N},
87  v_(storage_size_) {}
88 
89  /* getters */
90 
95  const storage_type& data() const { return v_; }
96 
101  idx size() const { return N_; }
102 
108  idx storage_size() const { return storage_size_; }
109 
110  // count the bits set to true
111  // (i.e. computes the Hamming distance)
116  idx count() const noexcept {
117  std::size_t result = 0;
118  for (idx i = 0; i < size(); ++i) {
119  if (this->get(i))
120  ++result;
121  }
122 
123  return result;
124  }
125 
126  // returns the bit at position pos
132  bool get(idx pos) const { return 1 & (v_[index_(pos)] >> offset_(pos)); }
133 
134  // returns true if none of the bits are set
139  bool none() const noexcept {
140  bool result = true;
141  for (idx i = 0; i < storage_size(); ++i) {
142  if (v_[i]) {
143  return false;
144  }
145  }
146 
147  return result;
148  }
149 
150  // returns true if all bits are set to true
155  bool all() const noexcept {
156  bool result = true;
157  for (idx i = 0; i < storage_size(); ++i) {
158  if (~v_[i]) {
159  return false;
160  }
161  }
162 
163  return result;
164  }
165 
166  // returns true if any bit is set to true
171  bool any() const noexcept { return !(this->none()); }
172 
173  /* setters */
174  // set the bit to a specific value
181  Dynamic_bitset& set(idx pos, bool value = true) {
182  value ? v_[index_(pos)] |= (1 << offset_(pos))
183  : v_[index_(pos)] &= ~(1 << offset_(pos));
184 
185  // v_[index_(pos)] &= ~(!value << offset_(pos));
186 
187  return *this;
188  }
189 
190  // sets all bits to true
195  Dynamic_bitset& set() noexcept {
196  for (idx i = 0; i < storage_size(); ++i) {
197  v_[i] = ~0;
198  }
199 
200  return *this;
201  }
202 
203  // set the bit according to a random Bernoulli(p) distribution
210  Dynamic_bitset& rand(idx pos, double p = 0.5) {
211  std::random_device rd;
212  std::mt19937 gen{rd()};
213  std::bernoulli_distribution d{p};
214 
215  this->set(pos, d(gen));
216 
217  return *this;
218  }
219 
220  // set all bits according to a random Bernoulli(p) distribution
226  Dynamic_bitset& rand(double p = 0.5) {
227  for (idx i = 0; i < size(); ++i) {
228  this->rand(i, p);
229  }
230 
231  return *this;
232  }
233 
234  // set the bit false
241  v_[index_(pos)] &= ~(1 << offset_(pos));
242 
243  return *this;
244  }
245 
246  // set all bits to 0
251  Dynamic_bitset& reset() noexcept {
252  for (idx i = 0; i < storage_size(); ++i) {
253  v_[i] = 0;
254  }
255 
256  return *this;
257  }
258 
259  // flips the bit
266  v_[index_(pos)] ^= 1 << (offset_(pos));
267 
268  return *this;
269  }
270 
271  // flip all bits
276  Dynamic_bitset& flip() noexcept {
277  for (idx i = 0; i < storage_size(); ++i) {
278  v_[i] = ~v_[i];
279  }
280 
281  return *this;
282  }
283 
284  /* operators */
290  bool operator==(const Dynamic_bitset& rhs) const noexcept {
291  assert(this->size() == rhs.size());
292  bool result = true;
293  idx n = std::min(this->storage_size(), rhs.storage_size());
294  for (idx i = 0; i < n; ++i) {
295  if (v_[i] != rhs.v_[i]) {
296  return false;
297  }
298  }
299 
300  return result;
301  }
302 
308  bool operator!=(const Dynamic_bitset& rhs) const noexcept {
309  return !(*this == rhs);
310  }
311 
312  /* input/output */
319  friend std::ostream& operator<<(std::ostream& os,
320  const Dynamic_bitset& rhs) {
321  for (idx i = rhs.size(); i-- > 0;) {
322  os << rhs.get(i);
323  }
324 
325  return os;
326  }
327 
337  template <class CharT = char, class Traits = std::char_traits<CharT>,
338  class Allocator = std::allocator<CharT>>
339  std::basic_string<CharT, Traits, Allocator>
340  to_string(CharT zero = CharT('0'), CharT one = CharT('1')) const {
341  std::basic_string<CharT, Traits, Allocator> result;
342  idx bitset_size = this->size();
343  result.resize(bitset_size);
344 
345  for (idx i = bitset_size; i-- > 0;) {
346  if (!this->get(i)) {
347  result[bitset_size - i - 1] = zero;
348  } else {
349  result[bitset_size - i - 1] = one;
350  }
351  }
352 
353  return result;
354  }
355 };
356 
361 class Bit_circuit : public Dynamic_bitset {
362  public:
363  // gate counters
364  struct Gate_count {
365  // 1 bit gates
366  idx NOT = 0;
367  idx& X = NOT;
368 
369  // 2 bit gates
370  idx CNOT = 0;
371  idx SWAP = 0;
372 
373  // 3 bit gates
374  idx FRED = 0;
375  idx TOF = 0;
376  } gate_count{};
377 
378  // inherit the constructor
380 
381  // flips the bit
382  Bit_circuit& X(idx pos) {
383  this->flip(pos);
384  ++gate_count.X;
385 
386  return *this;
387  }
388 
389  // flips the bit
391  this->flip(pos);
392  ++gate_count.NOT;
393 
394  return *this;
395  }
396 
397  // controlled-NOT control-target
398  Bit_circuit& CNOT(const std::vector<idx>& pos) {
399  v_[index_(pos[1])] ^= (1 & (v_[index_(pos[0])] >> offset_(pos[0])))
400  << offset_(pos[1]);
401  ++gate_count.CNOT;
402 
403  return *this;
404  }
405 
406  // Toffoli control-control-target
407  Bit_circuit& TOF(const std::vector<idx>& pos) {
408  v_[index_(pos[2])] ^= ((1 & (v_[index_(pos[1])] >> offset_(pos[1]))) &
409  (1 & (v_[index_(pos[0])] >> offset_(pos[0]))))
410  << offset_(pos[2]);
411 
412  ++gate_count.TOF;
413  return *this;
414  }
415 
416  // SWAP 2 bits
417  Bit_circuit& SWAP(const std::vector<idx>& pos) {
418  if (this->get(pos[0]) != this->get(pos[1])) {
419  this->X(pos[0]);
420  this->X(pos[1]);
421  }
422 
423  ++gate_count.SWAP;
424  return *this;
425  }
426 
427  // Fredkin gate
428  Bit_circuit& FRED(const std::vector<idx>& pos) {
429  if (this->get(pos[0])) {
430  this->SWAP({pos[1], pos[2]});
431  }
432 
433  ++gate_count.FRED;
434  return *this;
435  }
436 
437  // reset the circuit all zero, clear all gates
438  Bit_circuit& reset() noexcept {
439  gate_count.NOT = gate_count.X = 0;
440  gate_count.CNOT = gate_count.SWAP = 0;
441  gate_count.FRED = gate_count.TOF = 0;
442 
443  return *this;
444  }
445 };
446 
447 } /* namespace experimental */
448 } /* namespace qpp */
449 
450 #endif /* EXPERIMENTAL_EXPERIMENTAL_H_ */
bool all() const noexcept
Definition: experimental.h:155
Dynamic_bitset & rand(double p=0.5)
Definition: experimental.h:226
std::vector< value_type > v_
Storage space.
Definition: experimental.h:63
bool operator==(const Dynamic_bitset &rhs) const noexcept
Definition: experimental.h:290
friend std::ostream & operator<<(std::ostream &os, const Dynamic_bitset &rhs)
Definition: experimental.h:319
Bit_circuit & SWAP(const std::vector< idx > &pos)
Definition: experimental.h:417
Bit_circuit & X(idx pos)
Definition: experimental.h:382
idx N_
Number of bits.
Definition: experimental.h:62
Bit_circuit & TOF(const std::vector< idx > &pos)
Definition: experimental.h:407
Definition: experimental.h:364
Bit_circuit & FRED(const std::vector< idx > &pos)
Definition: experimental.h:428
Quantum++ main namespace.
Definition: codes.h:35
idx storage_size_
Storage size.
Definition: experimental.h:61
idx storage_size() const
Size of the underlying storage space (in units of value_type, unsigned int by default) ...
Definition: experimental.h:108
Dynamic_bitset & flip(idx pos)
Definition: experimental.h:265
Definition: experimental.h:361
Definition: experimental.h:56
Bit_circuit & NOT(idx pos)
Definition: experimental.h:390
Dynamic_bitset & reset(idx pos)
Definition: experimental.h:240
Bit_circuit & reset() noexcept
Definition: experimental.h:438
bool any() const noexcept
Definition: experimental.h:171
std::size_t idx
Definition: experimental.h:43
bool get(idx pos) const
Definition: experimental.h:132
unsigned int value_type
Type of the storage elements.
Definition: experimental.h:58
Bit_circuit & CNOT(const std::vector< idx > &pos)
Definition: experimental.h:398
bool operator!=(const Dynamic_bitset &rhs) const noexcept
Definition: experimental.h:308
idx count() const noexcept
Definition: experimental.h:116
bool none() const noexcept
Definition: experimental.h:139
Dynamic_bitset & rand(idx pos, double p=0.5)
Definition: experimental.h:210
idx size() const
Number of bits stored in the bitset.
Definition: experimental.h:101
Dynamic_bitset & flip() noexcept
Definition: experimental.h:276
std::size_t idx
Non-negative integer index.
Definition: types.h:39
Dynamic_bitset & reset() noexcept
Definition: experimental.h:251
idx offset_(idx pos) const
Offset of the pos bit in the storage space relative to its index.
Definition: experimental.h:78
idx index_(idx pos) const
Index of the pos bit in the storage space.
Definition: experimental.h:70
Dynamic_bitset(idx N)
Constructor, initializes all bits to false (zero)
Definition: experimental.h:85
const storage_type & data() const
Raw storage space of the bitset.
Definition: experimental.h:95
std::basic_string< CharT, Traits, Allocator > to_string(CharT zero=CharT('0'), CharT one=CharT('1')) const
Definition: experimental.h:340
std::vector< value_type > storage_type
Type of the storage.
Definition: experimental.h:59