1 // Copyright (C) 2008 Davis E. King (davis@dlib.net) 2 // License: Boost Software License See LICENSE.txt for the full license. 3 #undef DLIB_QUANTUM_COMPUTINg_ABSTRACT_ 4 #ifdef DLIB_QUANTUM_COMPUTINg_ABSTRACT_ 5 6 #include <complex> 7 #include "../matrix.h" 8 #include "../rand.h" 9 10 namespace dlib 11 { 12 13 // ---------------------------------------------------------------------------------------- 14 15 typedef std::complex<double> qc_scalar_type; 16 17 // ---------------------------------------------------------------------------------------- 18 19 class quantum_register 20 { 21 /*! 22 INITIAL VALUE 23 - num_bits() == 1 24 - state_vector().nr() == 2 25 - state_vector().nc() == 1 26 - state_vector()(0) == 1 27 - state_vector()(1) == 0 28 - probability_of_bit(0) == 0 29 30 - i.e. This register represents a single quantum bit and it is 31 completely in the 0 state. 32 33 WHAT THIS OBJECT REPRESENTS 34 This object represents a set of quantum bits. 35 !*/ 36 37 public: 38 39 quantum_register( 40 ); 41 /*! 42 ensures 43 - this object is properly initialized 44 !*/ 45 46 int num_bits ( 47 ) const; 48 /*! 49 ensures 50 - returns the number of quantum bits in this register 51 !*/ 52 53 void set_num_bits ( 54 int new_num_bits 55 ); 56 /*! 57 requires 58 - 1 <= new_num_bits <= 30 59 ensures 60 - #num_bits() == new_num_bits 61 - #state_vector().nr() == 2^new_num_bits 62 (i.e. the size of the state_vector is exponential in the number of bits in a register) 63 - for all valid i: 64 - probability_of_bit(i) == 0 65 !*/ 66 67 void zero_all_bits( 68 ); 69 /*! 70 ensures 71 - for all valid i: 72 - probability_of_bit(i) == 0 73 !*/ 74 75 void append ( 76 const quantum_register& reg 77 ); 78 /*! 79 ensures 80 - #num_bits() == num_bits() + reg.num_bits() 81 - #this->state_vector() == tensor_product(this->state_vector(), reg.state_vector()) 82 - The original bits in *this become the high order bits of the resulting 83 register and all the bits in reg end up as the low order bits in the 84 resulting register. 85 !*/ 86 87 double probability_of_bit ( 88 int bit 89 ) const; 90 /*! 91 requires 92 - 0 <= bit < num_bits() 93 ensures 94 - returns the probability of measuring the given bit and it being in the 1 state. 95 - The returned value is also equal to the sum of norm(state_vector()(i)) for all 96 i where the bit'th bit in i is set to 1. (note that the lowest order bit is bit 0) 97 !*/ 98 99 template <typename rand_type> 100 bool measure_bit ( 101 int bit, 102 rand_type& rnd 103 ); 104 /*! 105 requires 106 - 0 <= bit < num_bits() 107 - rand_type == an implementation of dlib/rand/rand_float_abstract.h 108 ensures 109 - measures the given bit in this register. Let R denote the boolean 110 result of the measurement, where true means the bit was measured to 111 have value 1 and false means it had a value of 0. 112 - if (R == true) then 113 - returns true 114 - #probability_of_bit(bit) == 1 115 - else 116 - returns false 117 - #probability_of_bit(bit) == 0 118 !*/ 119 120 template <typename rand_type> 121 bool measure_and_remove_bit ( 122 int bit, 123 rand_type& rnd 124 ); 125 /*! 126 requires 127 - num_bits() > 1 128 - 0 <= bit < num_bits() 129 - rand_type == an implementation of dlib/rand/rand_float_abstract.h 130 ensures 131 - measures the given bit in this register. Let R denote the boolean 132 result of the measurement, where true means the bit was measured to 133 have value 1 and false means it had a value of 0. 134 - #num_bits() == num_bits() - 1 135 - removes the bit that was measured from this register. 136 - if (R == true) then 137 - returns true 138 - else 139 - returns false 140 !*/ 141 142 const matrix<qc_scalar_type,0,1>& state_vector( 143 ) const; 144 /*! 145 ensures 146 - returns a const reference to the state vector that describes the state of 147 the quantum bits in this register. 148 !*/ 149 150 matrix<qc_scalar_type,0,1>& state_vector( 151 ); 152 /*! 153 ensures 154 - returns a non-const reference to the state vector that describes the state of 155 the quantum bits in this register. 156 !*/ 157 158 void swap ( 159 quantum_register& item 160 ); 161 /*! 162 ensures 163 - swaps *this and item 164 !*/ 165 166 }; 167 swap(quantum_register & a,quantum_register & b)168 inline void swap ( 169 quantum_register& a, 170 quantum_register& b 171 ) { a.swap(b); } 172 /*! 173 provides a global swap function 174 !*/ 175 176 // ---------------------------------------------------------------------------------------- 177 178 template <typename T> 179 class gate_exp 180 { 181 /*! 182 REQUIREMENTS ON T 183 T must be some object that inherits from gate_exp and implements its own 184 version of operator() and compute_state_element(). 185 186 WHAT THIS OBJECT REPRESENTS 187 This object represents an expression that evaluates to a quantum gate 188 that operates on T::num_bits qubits. 189 190 This object makes it easy to create new types of gate objects. All 191 you need to do is inherit from gate_exp in the proper way and 192 then you can use your new gate objects in conjunction with all the 193 others. 194 !*/ 195 196 public: 197 198 static const long num_bits = T::num_bits; 199 static const long dims = T::dims; 200 201 gate_exp( 202 T& exp 203 ); 204 /*! 205 ensures 206 - #&ref() == &exp 207 !*/ 208 209 const qc_scalar_type operator() ( 210 long r, 211 long c 212 ) const; 213 /*! 214 requires 215 - 0 <= r < dims 216 - 0 <= c < dims 217 ensures 218 - returns ref()(r,c) 219 !*/ 220 221 void apply_gate_to ( 222 quantum_register& reg 223 ) const; 224 /*! 225 requires 226 - reg.num_bits() == num_bits 227 ensures 228 - applies this quantum gate to the given quantum register 229 - Let M represent the matrix for this quantum gate, then 230 #reg().state_vector() = M*reg().state_vector() 231 !*/ 232 233 template <typename exp> 234 qc_scalar_type compute_state_element ( 235 const matrix_exp<exp>& reg, 236 long row_idx 237 ) const; 238 /*! 239 requires 240 - reg.nr() == dims 241 - reg.nc() == 1 242 - 0 <= row_idx < dims 243 ensures 244 - Let M represent the matrix for this gate, then 245 this function returns rowm(M*reg, row_idx) 246 (i.e. returns the row_idx row of what you get when you apply this 247 gate to the given column vector in reg) 248 - This function works by calling ref().compute_state_element(reg,row_idx) 249 !*/ 250 251 const T& ref( 252 ); 253 /*! 254 ensures 255 - returns a reference to the subexpression contained in this object 256 !*/ 257 258 const matrix<qc_scalar_type> mat ( 259 ) const; 260 /*! 261 ensures 262 - returns a dense matrix object that contains the matrix for this gate 263 !*/ 264 }; 265 266 // ---------------------------------------------------------------------------------------- 267 268 template <typename T, typename U> 269 class composite_gate : public gate_exp<composite_gate<T,U> > 270 { 271 /*! 272 REQUIREMENTS ON T AND U 273 Both must be gate expressions that inherit from gate_exp 274 275 WHAT THIS OBJECT REPRESENTS 276 This object represents a quantum gate that is the tensor product of 277 two other quantum gates. 278 279 280 As an example, suppose you have 3 registers, reg_high, reg_low, and reg_all. Also 281 suppose that reg_all is what you get when you append reg_high and reg_low, 282 so reg_all.state_vector() == tensor_product(reg_high.state_vector(),reg_low.state_vector()). 283 284 Then applying a composite gate to reg_all would give you the same thing as 285 applying the lhs gate to reg_high and the rhs gate to reg_low and then appending 286 the two resulting registers. So the lhs gate of a composite_gate applies to 287 the high order bits of a regitser and the rhs gate applies to the lower order bits. 288 !*/ 289 public: 290 291 composite_gate ( 292 const composite_gate& g 293 ); 294 /*! 295 ensures 296 - *this is a copy of g 297 !*/ 298 299 composite_gate( 300 const gate_exp<T>& lhs_, 301 const gate_exp<U>& rhs_ 302 ): 303 /*! 304 ensures 305 - #lhs == lhs_.ref() 306 - #rhs == rhs_.ref() 307 - #num_bits == T::num_bits + U::num_bits 308 - #dims == 2^num_bits 309 - #&ref() == this 310 !*/ 311 312 const qc_scalar_type operator() ( 313 long r, 314 long c 315 ) const; 316 /*! 317 requires 318 - 0 <= r < dims 319 - 0 <= c < dims 320 ensures 321 - Let M denote the tensor product of lhs with rhs, then this function 322 returns M(r,c) 323 (i.e. returns lhs(r/U::dims,c/U::dims)*rhs(r%U::dims, c%U::dims)) 324 !*/ 325 326 template <typename exp> 327 qc_scalar_type compute_state_element ( 328 const matrix_exp<exp>& reg, 329 long row_idx 330 ) const; 331 /*! 332 requires 333 - reg.nr() == dims 334 - reg.nc() == 1 335 - 0 <= row_idx < dims 336 ensures 337 - Let M represent the matrix for this gate, then this function 338 returns rowm(M*reg, row_idx) 339 (i.e. returns the row_idx row of what you get when you apply this 340 gate to the given column vector in reg) 341 - This function works by calling rhs.compute_state_element() and using elements 342 of the matrix in lhs. 343 !*/ 344 345 static const long num_bits; 346 static const long dims; 347 348 const T lhs; 349 const U rhs; 350 }; 351 352 // ---------------------------------------------------------------------------------------- 353 354 template <long bits> 355 class gate : public gate_exp<gate<bits> > 356 { 357 /*! 358 REQUIREMENTS ON bits 359 0 < bits <= 30 360 361 WHAT THIS OBJECT REPRESENTS 362 This object represents a quantum gate that operates on bits qubits. 363 It stores its gate matrix explicitly in a dense in-memory matrix. 364 !*/ 365 366 public: 367 gate( 368 ); 369 /*! 370 ensures 371 - num_bits == bits 372 - dims == 2^bits 373 - #&ref() == this 374 - for all valid r and c: 375 #(*this)(r,c) == 0 376 !*/ 377 378 gate ( 379 const gate& g 380 ); 381 /*! 382 ensures 383 - *this is a copy of g 384 !*/ 385 386 template <typename T> 387 explicit gate( 388 const gate_exp<T>& g 389 ); 390 /*! 391 requires 392 - T::num_bits == num_bits 393 ensures 394 - num_bits == bits 395 - dims == 2^bits 396 - #&ref() == this 397 - for all valid r and c: 398 #(*this)(r,c) == g(r,c) 399 !*/ 400 401 const qc_scalar_type& operator() ( 402 long r, 403 long c 404 ) const; 405 /*! 406 requires 407 - 0 <= r < dims 408 - 0 <= c < dims 409 ensures 410 - Let M denote the matrix for this gate, then this function 411 returns a const reference to M(r,c) 412 !*/ 413 414 qc_scalar_type& operator() ( 415 long r, 416 long c 417 ); 418 /*! 419 requires 420 - 0 <= r < dims 421 - 0 <= c < dims 422 ensures 423 - Let M denote the matrix for this gate, then this function 424 returns a non-const reference to M(r,c) 425 !*/ 426 427 template <typename exp> 428 qc_scalar_type compute_state_element ( 429 const matrix_exp<exp>& reg, 430 long row_idx 431 ) const; 432 /*! 433 requires 434 - reg.nr() == dims 435 - reg.nc() == 1 436 - 0 <= row_idx < dims 437 ensures 438 - Let M represent the matrix for this gate, then this function 439 returns rowm(M*reg, row_idx) 440 (i.e. returns the row_idx row of what you get when you apply this 441 gate to the given column vector in reg) 442 !*/ 443 444 static const long num_bits; 445 static const long dims; 446 447 }; 448 449 // ---------------------------------------------------------------------------------------- 450 451 template <typename T, typename U> 452 const composite_gate<T,U> operator, ( 453 const gate_exp<T>& lhs, 454 const gate_exp<U>& rhs 455 ) { return composite_gate<T,U>(lhs,rhs); } 456 /*! 457 ensures 458 - returns a composite_gate that represents the tensor product of the lhs 459 gate with the rhs gate. 460 !*/ 461 462 // ---------------------------------------------------------------------------------------- 463 464 namespace quantum_gates 465 { 466 467 inline const gate<1> hadamard( 468 ); 469 /*! 470 ensures 471 - returns the Hadamard gate. 472 (i.e. A gate with a matrix of 473 |1, 1| 474 1/sqrt(2) * |1,-1| ) 475 !*/ 476 477 inline const gate<1> x( 478 ); 479 /*! 480 ensures 481 - returns the not gate. 482 (i.e. A gate with a matrix of 483 |0, 1| 484 |1, 0| ) 485 !*/ 486 487 inline const gate<1> y( 488 ); 489 /*! 490 ensures 491 - returns the y gate. 492 (i.e. A gate with a matrix of 493 |0,-i| 494 |i, 0| ) 495 !*/ 496 497 inline const gate<1> z( 498 ); 499 /*! 500 ensures 501 - returns the z gate. 502 (i.e. A gate with a matrix of 503 |1, 0| 504 |0,-1| ) 505 !*/ 506 507 inline const gate<1> noop( 508 ); 509 /*! 510 ensures 511 - returns the no-op or identity gate. 512 (i.e. A gate with a matrix of 513 |1, 0| 514 |0, 1| ) 515 !*/ 516 517 template < 518 int control_bit, 519 int target_bit 520 > 521 class cnot : public gate_exp<cnot<control_bit, target_bit> > 522 { 523 /*! 524 REQUIREMENTS ON control_bit AND target_bit 525 - control_bit != target_bit 526 527 WHAT THIS OBJECT REPRESENTS 528 This object represents the controlled-not quantum gate. It is a gate that 529 operates on abs(control_bit-target_bit)+1 qubits. 530 531 In terms of the computational basis vectors, this gate maps input 532 vectors to output vectors in the following way: 533 - if (the input vector corresponds to a state where the control_bit 534 qubit is 1) then 535 - this gate outputs the computational basis vector that 536 corresponds to the state where the target_bit has been flipped 537 with respect to the input vector 538 - else 539 - this gate outputs the input vector unmodified 540 541 !*/ 542 }; 543 544 template < 545 int control_bit1, 546 int control_bit2, 547 int target_bit 548 > 549 class toffoli : public gate_exp<toffoli<control_bit1, control_bit2, target_bit> > 550 { 551 /*! 552 REQUIREMENTS ON control_bit1, control_bit2, AND target_bit 553 - all the arguments denote different bits, i.e.: 554 - control_bit1 != target_bit 555 - control_bit2 != target_bit 556 - control_bit1 != control_bit2 557 - The target bit can't be in-between the control bits, i.e.: 558 - (control_bit1 < target_bit && control_bit2 < target_bit) || 559 (control_bit1 > target_bit && control_bit2 > target_bit) 560 561 WHAT THIS OBJECT REPRESENTS 562 This object represents the toffoli variant of a controlled-not quantum gate. 563 It is a gate that operates on max(abs(control_bit2-target_bit),abs(control_bit1-target_bit))+1 564 qubits. 565 566 In terms of the computational basis vectors, this gate maps input 567 vectors to output vectors in the following way: 568 - if (the input vector corresponds to a state where the control_bit1 and 569 control_bit2 qubits are 1) then 570 - this gate outputs the computational basis vector that 571 corresponds to the state where the target_bit has been flipped 572 with respect to the input vector 573 - else 574 - this gate outputs the input vector unmodified 575 576 !*/ 577 }; 578 579 // ------------------------------------------------------------------------------------ 580 581 } 582 583 // ---------------------------------------------------------------------------------------- 584 585 } 586 587 #endif // DLIB_QUANTUM_COMPUTINg_ABSTRACT_ 588 589 590 591