microsoft/qdk
Publicmirrored fromhttps://github.com/microsoft/qdkAvailable
library/std/src/Std/Arithmetic.qs
730lines · modecode
| 1 | // Copyright (c) Microsoft Corporation. |
| 2 | // Licensed under the MIT License. |
| 3 | |
| 4 | import |
| 5 | Std.ArithmeticUtils.*, |
| 6 | Std.Arrays.Most, |
| 7 | Std.Arrays.Tail, |
| 8 | Std.Arrays.Head, |
| 9 | Std.Arrays.Rest, |
| 10 | Std.Arrays.IndexRange, |
| 11 | Std.Diagnostics.Fact, |
| 12 | Std.Math.MinI, |
| 13 | Std.Math.TrailingZeroCountL, |
| 14 | Std.Math.TrailingZeroCountI, |
| 15 | Std.Math.BitSizeL, |
| 16 | Std.Convert.BigIntAsBoolArray; |
| 17 | |
| 18 | /// # Summary |
| 19 | /// This applies the in-place majority operation to 3 qubits. |
| 20 | /// |
| 21 | /// # Description |
| 22 | /// Assuming the state of the input qubits are |x⟩, |y⟩ and |z⟩, then |
| 23 | /// this operation performs the following transformation: |
| 24 | /// |x⟩|y⟩|z⟩ ↦ |x ⊕ z⟩|y ⊕ z⟩MAJ(x, y, z). |
| 25 | /// |
| 26 | /// # Input |
| 27 | /// ## x |
| 28 | /// The first input qubit. |
| 29 | /// ## y |
| 30 | /// The second input qubit. |
| 31 | /// ## z |
| 32 | /// A qubit onto which the majority function will be applied. |
| 33 | operation MAJ(x : Qubit, y : Qubit, z : Qubit) : Unit is Adj + Ctl { |
| 34 | CNOT(z, y); |
| 35 | CNOT(z, x); |
| 36 | CCNOT(y, x, z); |
| 37 | } |
| 38 | |
| 39 | /// # Summary |
| 40 | /// Reflects a quantum register about a given classical integer. |
| 41 | /// |
| 42 | /// # Description |
| 43 | /// Given a quantum register initially in the state ∑ᵢ(αᵢ|i⟩), |
| 44 | /// where each |i⟩ is a basis state representing an integer i, |
| 45 | /// reflects the state of the register about the basis state |j⟩ |
| 46 | /// for a given integer j: ∑ᵢ(-1)^(δᵢⱼ)(αᵢ|i⟩) |
| 47 | /// This operation is implemented in-place, without explicit allocation of |
| 48 | /// additional auxiliary qubits. |
| 49 | /// |
| 50 | /// # Input |
| 51 | /// ## index |
| 52 | /// The classical integer j indexing the basis state about which to reflect. |
| 53 | /// ## reg |
| 54 | /// Little-endian quantum register to reflect. |
| 55 | operation ReflectAboutInteger(index : Int, reg : Qubit[]) : Unit is Adj + Ctl { |
| 56 | within { |
| 57 | // Evaluation optimization for case index == 0 |
| 58 | if index == 0 { |
| 59 | ApplyToEachA(X, reg); |
| 60 | } else { |
| 61 | // We want to reduce to the problem of reflecting about the all-ones |
| 62 | // state. To do that, we apply our reflection within an application |
| 63 | // of X instructions that flip all the zeros in our index. |
| 64 | ApplyPauliFromInt(PauliX, false, index, reg); |
| 65 | } |
| 66 | } apply { |
| 67 | Controlled ApplyAsSinglyControlled(Most(reg), (Z, Tail(reg))); |
| 68 | } |
| 69 | } |
| 70 | |
| 71 | // |
| 72 | // Add, Increment | Operation | Description |
| 73 | // ____________________|________________|_______________________________________________________________ |
| 74 | // y += 5 | IncByI, IncByL | Increment LE register in-place by integer |
| 75 | // y += x | IncByLE | Increment LE register in-place by LE register |
| 76 | // z = x + 5 (z was 0) | | Add integer to LE register creating result out-of-place |
| 77 | // z = x + y (z was 0) | AddLE | Add two LE register creating result out-of-place |
| 78 | // z += x + 5 | | Increment LE register by the sum of integer and LE register |
| 79 | // z += x + y | | Increment LE register by the sum of two LE registers |
| 80 | // |
| 81 | // IncByLE implementations: |
| 82 | // RippleCarryTTKIncByLE (default) |
| 83 | // RippleCarryCGIncByLE |
| 84 | // FourierTDIncByLE |
| 85 | // via IncByLEUsingAddLE and any out-of-place addition |
| 86 | // IncByI implementations: |
| 87 | // via IncByIUsingIncByLE and any in-place LE adder |
| 88 | // IncByL implementations: |
| 89 | // via IncByLUsingIncByLE and any in-place LE adder |
| 90 | // AddLE implementations: |
| 91 | // RippleCarryCGAddLE (default) |
| 92 | // LookAheadDKRSAddLE |
| 93 | // |
| 94 | |
| 95 | /// # Summary |
| 96 | /// Increments a little-endian register ys by an integer number c |
| 97 | /// |
| 98 | /// # Description |
| 99 | /// Computes ys += c modulo 2ⁿ, where ys is a little-endian register, |
| 100 | /// Length(ys) = n > 0, c is a Int number, 0 ≤ c < 2ⁿ. |
| 101 | /// NOTE: Use IncByIUsingIncByLE directly if the choice of implementation |
| 102 | /// is important. |
| 103 | operation IncByI(c : Int, ys : Qubit[]) : Unit is Adj + Ctl { |
| 104 | IncByIUsingIncByLE(RippleCarryTTKIncByLE, c, ys); |
| 105 | } |
| 106 | |
| 107 | /// # Summary |
| 108 | /// Increments a little-endian register ys by a BigInt number c |
| 109 | /// |
| 110 | /// # Description |
| 111 | /// Computes ys += c modulo 2ⁿ, where ys is a little-endian register, |
| 112 | /// Length(ys) = n > 0, c is a BigInt number, 0 ≤ c < 2ⁿ. |
| 113 | /// NOTE: Use IncByLUsingIncByLE directly if the choice of implementation |
| 114 | /// is important. |
| 115 | operation IncByL(c : BigInt, ys : Qubit[]) : Unit is Adj + Ctl { |
| 116 | IncByLUsingIncByLE(RippleCarryTTKIncByLE, c, ys); |
| 117 | } |
| 118 | |
| 119 | /// # Summary |
| 120 | /// Increments a little-endian register ys by a little-endian register xs |
| 121 | /// |
| 122 | /// # Description |
| 123 | /// Computes ys += xs modulo 2ⁿ, where xs and ys are little-endian registers, |
| 124 | /// and Length(xs) ≤ Length(ys) = n. |
| 125 | /// NOTE: Use operations like RippleCarryCGIncByLE directly if |
| 126 | /// the choice of implementation is important. |
| 127 | operation IncByLE(xs : Qubit[], ys : Qubit[]) : Unit is Adj + Ctl { |
| 128 | RippleCarryTTKIncByLE(xs, ys); |
| 129 | } |
| 130 | |
| 131 | /// # Summary |
| 132 | /// Sets a zero-initialized little-endian register zs to the sum of |
| 133 | /// little-endian registers xs and ys |
| 134 | /// |
| 135 | /// # Description |
| 136 | /// Computes zs := xs + ys modulo 2ⁿ, where xs, ys, and zs are little-endian registers, |
| 137 | /// Length(xs) = Length(ys) ≤ Length(zs) = n, assuming zs is 0-initialized. |
| 138 | /// NOTE: Use operations like RippleCarryCGAddLE directly if |
| 139 | /// the choice of implementation is important. |
| 140 | operation AddLE(xs : Qubit[], ys : Qubit[], zs : Qubit[]) : Unit is Adj { |
| 141 | RippleCarryCGAddLE(xs, ys, zs); |
| 142 | } |
| 143 | |
| 144 | /// # Summary |
| 145 | /// Reversible, in-place ripple-carry addition of two integers. |
| 146 | /// |
| 147 | /// # Description |
| 148 | /// Computes ys += xs modulo 2ⁿ, where xs and ys are little-endian registers, |
| 149 | /// and Length(xs) ≤ Length(ys) = n. |
| 150 | /// This operation uses the ripple-carry algorithm. |
| 151 | /// Note that if Length(ys) >= Length(xs)+2, xs is padded with 0-initialized |
| 152 | /// qubits to match ys's length. The operation doesn't use any auxiliary |
| 153 | /// qubits otherwise. |
| 154 | /// |
| 155 | /// # References |
| 156 | /// - [arXiv:0910.2530](https://arxiv.org/abs/0910.2530) |
| 157 | /// "Quantum Addition Circuits and Unbounded Fan-Out", |
| 158 | /// Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro |
| 159 | operation RippleCarryTTKIncByLE(xs : Qubit[], ys : Qubit[]) : Unit is Adj + Ctl { |
| 160 | let xsLen = Length(xs); |
| 161 | let ysLen = Length(ys); |
| 162 | |
| 163 | Fact(ysLen >= xsLen, "Register `ys` must be longer than register `xs`."); |
| 164 | Fact(xsLen >= 1, "Registers `xs` and `ys` must contain at least one qubit."); |
| 165 | |
| 166 | if xsLen == ysLen { |
| 167 | if xsLen > 1 { |
| 168 | within { |
| 169 | ApplyOuterTTKAdder(xs, ys); |
| 170 | } apply { |
| 171 | ApplyInnerTTKAdderNoCarry(xs, ys); |
| 172 | } |
| 173 | } |
| 174 | CNOT(xs[0], ys[0]); |
| 175 | } elif xsLen + 1 == ysLen { |
| 176 | if xsLen > 1 { |
| 177 | CNOT(xs[xsLen - 1], ys[ysLen - 1]); |
| 178 | within { |
| 179 | ApplyOuterTTKAdder(xs, ys); |
| 180 | } apply { |
| 181 | ApplyInnerTTKAdderWithCarry(xs, ys); |
| 182 | } |
| 183 | } else { |
| 184 | CCNOT(xs[0], ys[0], ys[1]); |
| 185 | } |
| 186 | CNOT(xs[0], ys[0]); |
| 187 | } elif xsLen + 2 <= ysLen { |
| 188 | // Pad xs so that its length is one qubit shorter than ys. |
| 189 | use padding = Qubit[ysLen - xsLen - 1]; |
| 190 | RippleCarryTTKIncByLE(xs + padding, ys); |
| 191 | } |
| 192 | } |
| 193 | |
| 194 | /// # Summary |
| 195 | /// Increments a little-endian register ys by a little-endian register xs |
| 196 | /// using the ripple-carry algorithm. |
| 197 | /// |
| 198 | /// # Description |
| 199 | /// Computes ys += xs modulo 2ⁿ, where xs and ys are little-endian registers, |
| 200 | /// and Length(xs) ≤ Length(ys) = n. |
| 201 | /// Note that if Length(xs) != Length(ys), xs is padded with 0-initialized |
| 202 | /// qubits to match ys's length. |
| 203 | /// This operation uses the ripple-carry algorithm. |
| 204 | /// |
| 205 | /// # Reference |
| 206 | /// - [arXiv:1709.06648](https://arxiv.org/pdf/1709.06648.pdf) |
| 207 | /// "Halving the cost of quantum addition", Craig Gidney. |
| 208 | operation RippleCarryCGIncByLE(xs : Qubit[], ys : Qubit[]) : Unit is Adj + Ctl { |
| 209 | let xsLen = Length(xs); |
| 210 | let ysLen = Length(ys); |
| 211 | |
| 212 | Fact(ysLen >= xsLen, "Register `ys` must be longer than register `xs`."); |
| 213 | Fact(xsLen >= 1, "Registers `xs` and `ys` must contain at least one qubit."); |
| 214 | |
| 215 | if ysLen - xsLen >= 2 { |
| 216 | // Pad xs so that its length is one qubit shorter than ys. |
| 217 | use padding = Qubit[ysLen - xsLen - 1]; |
| 218 | RippleCarryCGIncByLE(xs + padding, ys); |
| 219 | } elif xsLen == 1 { |
| 220 | if ysLen == 1 { |
| 221 | CNOT(xs[0], ys[0]); |
| 222 | } elif ysLen == 2 { |
| 223 | HalfAdderForInc(xs[0], ys[0], ys[1]); |
| 224 | } |
| 225 | } else { |
| 226 | use carries = Qubit[xsLen]; |
| 227 | within { |
| 228 | AND(xs[0], ys[0], carries[0]); |
| 229 | } apply { |
| 230 | for i in 1..xsLen - 2 { |
| 231 | CarryForInc(carries[i - 1], xs[i], ys[i], carries[i]); |
| 232 | } |
| 233 | if xsLen == ysLen { |
| 234 | within { |
| 235 | CNOT(carries[xsLen - 2], xs[xsLen - 1]); |
| 236 | } apply { |
| 237 | CNOT(xs[xsLen - 1], ys[xsLen - 1]); |
| 238 | } |
| 239 | } else { |
| 240 | FullAdderForInc(carries[xsLen - 2], xs[xsLen - 1], ys[xsLen - 1], ys[xsLen]); |
| 241 | } |
| 242 | for i in xsLen - 2..-1..1 { |
| 243 | UncarryForInc(carries[i - 1], xs[i], ys[i], carries[i]); |
| 244 | } |
| 245 | } |
| 246 | CNOT(xs[0], ys[0]); |
| 247 | } |
| 248 | } |
| 249 | |
| 250 | /// # Summary |
| 251 | /// Sets a zero-initialized little-endian register zs to the sum of |
| 252 | /// little-endian registers xs and ys using the ripple-carry algorithm. |
| 253 | /// |
| 254 | /// # Description |
| 255 | /// Computes zs := xs + ys + zs[0] modulo 2ⁿ, where xs, ys, and zs are |
| 256 | /// little-endian registers, Length(xs) = Length(ys) ≤ Length(zs) = n, |
| 257 | /// assuming zs is 0-initialized, except for maybe zs[0], which can be |
| 258 | // in |0> or |1> state and can be used as carry-in. |
| 259 | /// This operation uses the ripple-carry algorithm. |
| 260 | /// NOTE: `zs[Length(xs)]` can be used as carry-out, if `zs` is longer than `xs`. |
| 261 | /// |
| 262 | /// # Reference |
| 263 | /// - [arXiv:1709.06648](https://arxiv.org/pdf/1709.06648.pdf) |
| 264 | /// "Halving the cost of quantum addition", Craig Gidney. |
| 265 | operation RippleCarryCGAddLE(xs : Qubit[], ys : Qubit[], zs : Qubit[]) : Unit is Adj { |
| 266 | let xsLen = Length(xs); |
| 267 | let zsLen = Length(zs); |
| 268 | Fact(Length(ys) == xsLen, "Registers `xs` and `ys` must be of same length."); |
| 269 | Fact(zsLen >= xsLen, "Register `zs` must be no shorter than register `xs`."); |
| 270 | |
| 271 | // Since zs is zero-initialized, its bits at indexes higher than |
| 272 | // xsLen remain unused as there will be no carry into them. |
| 273 | let top = MinI(zsLen - 2, xsLen - 1); |
| 274 | for k in 0..top { |
| 275 | FullAdder(zs[k], xs[k], ys[k], zs[k + 1]); |
| 276 | } |
| 277 | |
| 278 | if xsLen > 0 and xsLen == zsLen { |
| 279 | CNOT(Tail(xs), Tail(zs)); |
| 280 | CNOT(Tail(ys), Tail(zs)); |
| 281 | } |
| 282 | } |
| 283 | |
| 284 | /// # Summary |
| 285 | /// Sets a zero-initialized little-endian register zs to the sum of |
| 286 | /// little-endian registers xs and ys using the carry-lookahead algorithm. |
| 287 | /// |
| 288 | /// # Description |
| 289 | /// Computes zs := xs + ys + zs[0] modulo 2ⁿ, where xs, ys, and zs are |
| 290 | /// little-endian registers, Length(xs) = Length(ys) ≤ Length(zs) = n, |
| 291 | /// assuming zs is 0-initialized, except for maybe zs[0], which can be |
| 292 | /// in |0> or |1> state and can be used as carry-in. |
| 293 | /// NOTE: `zs[Length(xs)]` can be used as carry-out, if `zs` is longer than `xs`. |
| 294 | /// This operation uses the carry-lookahead algorithm. |
| 295 | /// |
| 296 | /// # Reference |
| 297 | /// - [arXiv:quant-ph/0406142](https://arxiv.org/abs/quant-ph/0406142) |
| 298 | /// "A logarithmic-depth quantum carry-lookahead adder", |
| 299 | /// Thomas G. Draper, Samuel A. Kutin, Eric M. Rains, Krysta M. Svore |
| 300 | operation LookAheadDKRSAddLE(xs : Qubit[], ys : Qubit[], zs : Qubit[]) : Unit is Adj { |
| 301 | let xsLen = Length(xs); |
| 302 | let zsLen = Length(zs); |
| 303 | Fact(Length(ys) == xsLen, "Registers `xs` and `ys` must be of same length."); |
| 304 | Fact(zsLen >= xsLen, "Register `zs` must be no shorter than register `xs`."); |
| 305 | |
| 306 | if zsLen > xsLen { |
| 307 | // with carry-out |
| 308 | // compute initial generate values |
| 309 | for k in 0..xsLen - 1 { |
| 310 | AND(xs[k], ys[k], zs[k + 1]); |
| 311 | } |
| 312 | |
| 313 | within { |
| 314 | // compute initial propagate values |
| 315 | for i in IndexRange(xs) { |
| 316 | CNOT(xs[i], ys[i]); |
| 317 | } |
| 318 | } apply { |
| 319 | ComputeCarries(ys, zs[0..xsLen]); |
| 320 | |
| 321 | // compute sum into carries |
| 322 | for k in 0..xsLen - 1 { |
| 323 | CNOT(ys[k], zs[k]); |
| 324 | } |
| 325 | } |
| 326 | } else { |
| 327 | // xsLen == zsLen, so without carry-out |
| 328 | LookAheadDKRSAddLE(Most(xs), Most(ys), zs); |
| 329 | CNOT(Tail(xs), Tail(zs)); |
| 330 | CNOT(Tail(ys), Tail(zs)); |
| 331 | } |
| 332 | } |
| 333 | |
| 334 | /// # Summary |
| 335 | /// Increments a little-endian register ys by a little-endian register xs |
| 336 | /// using Quantum Fourier Transform. |
| 337 | /// |
| 338 | /// # Description |
| 339 | /// Computes ys += xs modulo 2ⁿ, where xs and ys are little-endian registers, |
| 340 | /// and Length(xs) = Length(ys) = n. |
| 341 | /// This operation uses Quantum Fourier Transform. |
| 342 | /// |
| 343 | /// # Reference |
| 344 | /// - [arXiv:quant-ph/0008033](https://arxiv.org/abs/quant-ph/0008033) |
| 345 | /// "Addition on a Quantum Computer", Thomas G. Draper |
| 346 | operation FourierTDIncByLE(xs : Qubit[], ys : Qubit[]) : Unit is Adj + Ctl { |
| 347 | within { |
| 348 | ApplyQFT(ys); |
| 349 | } apply { |
| 350 | for i in IndexRange(xs) { |
| 351 | Controlled PhaseGradient([xs[i]], ys[i...]); |
| 352 | } |
| 353 | } |
| 354 | } |
| 355 | |
| 356 | /// # Summary |
| 357 | /// Increments a little-endian register ys by a BigInt number c |
| 358 | /// using provided adder. |
| 359 | /// |
| 360 | /// # Description |
| 361 | /// Computes ys += c modulo 2ⁿ, where ys is a little-endian register |
| 362 | /// Length(ys) = n > 0, c is a BigInt number, 0 ≤ c < 2ⁿ. |
| 363 | operation IncByLUsingIncByLE( |
| 364 | adder : (Qubit[], Qubit[]) => Unit is Adj + Ctl, |
| 365 | c : BigInt, |
| 366 | ys : Qubit[] |
| 367 | ) : Unit is Adj + Ctl { |
| 368 | |
| 369 | let ysLen = Length(ys); |
| 370 | Fact(ysLen > 0, "Length of `ys` must be at least 1."); |
| 371 | Fact(c >= 0L, "Constant `c` must be non-negative."); |
| 372 | Fact(c < 2L^ysLen, "Constant `c` must be smaller than 2^Length(ys)."); |
| 373 | |
| 374 | if c != 0L { |
| 375 | // If c has j trailing zeros, then the j least significant |
| 376 | // bits of y won't be affected by the addition and can |
| 377 | // therefore be ignored by applying the addition only to |
| 378 | // the other qubits and shifting c accordingly. |
| 379 | let j = TrailingZeroCountL(c); |
| 380 | use x = Qubit[ysLen - j]; |
| 381 | within { |
| 382 | ApplyXorInPlaceL(c >>> j, x); |
| 383 | } apply { |
| 384 | adder(x, ys[j...]); |
| 385 | } |
| 386 | } |
| 387 | } |
| 388 | |
| 389 | /// # Summary |
| 390 | /// Increments a little-endian register ys by an Int number c |
| 391 | /// using provided adder. |
| 392 | /// |
| 393 | /// # Description |
| 394 | /// Computes ys += c modulo 2ⁿ, where ys is a little-endian register |
| 395 | /// Length(ys) = n > 0, c is an Int number, 0 ≤ c < 2ⁿ. |
| 396 | operation IncByIUsingIncByLE( |
| 397 | adder : (Qubit[], Qubit[]) => Unit is Adj + Ctl, |
| 398 | c : Int, |
| 399 | ys : Qubit[] |
| 400 | ) : Unit is Adj + Ctl { |
| 401 | |
| 402 | let ysLen = Length(ys); |
| 403 | Fact(ysLen > 0, "Length of `ys` must be at least 1."); |
| 404 | Fact(c >= 0, "Constant `c` must be non-negative."); |
| 405 | Fact(c < 2^ysLen, "Constant `c` must be smaller than 2^Length(ys)."); |
| 406 | |
| 407 | if c != 0 { |
| 408 | // If c has j trailing zeros than the j least significant |
| 409 | // bits of y won't be affected by the addition and can |
| 410 | // therefore be ignored by applying the addition only to |
| 411 | // the other qubits and shifting c accordingly. |
| 412 | let j = TrailingZeroCountI(c); |
| 413 | use x = Qubit[ysLen - j]; |
| 414 | within { |
| 415 | ApplyXorInPlace(c >>> j, x); |
| 416 | } apply { |
| 417 | adder(x, ys[j...]); |
| 418 | } |
| 419 | } |
| 420 | } |
| 421 | |
| 422 | /// # Summary |
| 423 | /// Generic operation to turn two out-place adders into one in-place adder |
| 424 | /// |
| 425 | /// # Description |
| 426 | /// This implementation allows to specify two distinct adders for forward |
| 427 | /// and backward direction. The forward adder is always applied in its |
| 428 | /// body variant, whereas the backward adder is always applied in its adjoint |
| 429 | /// variant. Therefore, it's possible to, for example, use the ripple-carry |
| 430 | /// out-of-place adder in backwards direction to require no T gates. |
| 431 | /// |
| 432 | /// The controlled variant is also optimized in a way that everything but |
| 433 | /// the adders is controlled, |
| 434 | /// |
| 435 | /// # Reference |
| 436 | /// - [arXiv:2012.01624](https://arxiv.org/abs/2012.01624) |
| 437 | /// "Quantum block lookahead adders and the wait for magic states", |
| 438 | /// Craig Gidney. |
| 439 | operation IncByLEUsingAddLE( |
| 440 | forwardAdder : (Qubit[], Qubit[], Qubit[]) => Unit is Adj, |
| 441 | backwardAdder : (Qubit[], Qubit[], Qubit[]) => Unit is Adj, |
| 442 | xs : Qubit[], |
| 443 | ys : Qubit[] |
| 444 | ) : Unit is Adj + Ctl { |
| 445 | |
| 446 | body (...) { |
| 447 | let n = Length(xs); |
| 448 | |
| 449 | Fact(Length(ys) == n, "Registers xs and ys must be of same length"); |
| 450 | |
| 451 | use qs = Qubit[n]; |
| 452 | |
| 453 | forwardAdder(xs, ys, qs); |
| 454 | for i in IndexRange(ys) { |
| 455 | SWAP(ys[i], qs[i]); |
| 456 | } |
| 457 | ApplyToEachA(X, qs); |
| 458 | within { |
| 459 | ApplyToEachA(X, ys); |
| 460 | } apply { |
| 461 | Adjoint backwardAdder(xs, ys, qs); |
| 462 | } |
| 463 | } |
| 464 | adjoint (...) { |
| 465 | let n = Length(xs); |
| 466 | |
| 467 | Fact(Length(ys) == n, "Registers xs and ys must be of same length"); |
| 468 | |
| 469 | use qs = Qubit[n]; |
| 470 | |
| 471 | within { |
| 472 | ApplyToEachA(X, ys); |
| 473 | } apply { |
| 474 | forwardAdder(xs, ys, qs); |
| 475 | } |
| 476 | ApplyToEachA(X, qs); |
| 477 | for i in IndexRange(ys) { |
| 478 | SWAP(ys[i], qs[i]); |
| 479 | } |
| 480 | Adjoint backwardAdder(xs, ys, qs); |
| 481 | } |
| 482 | controlled (ctls, ...) { |
| 483 | // When we control everything except the adders, the adders will |
| 484 | // cancel themselves. |
| 485 | let n = Length(xs); |
| 486 | |
| 487 | Fact(Length(ys) == n, "Registers xs and ys must be of same length"); |
| 488 | |
| 489 | use qs = Qubit[n]; |
| 490 | |
| 491 | forwardAdder(xs, ys, qs); |
| 492 | for i in IndexRange(ys) { |
| 493 | Controlled SWAP(ctls, (ys[i], qs[i])) |
| 494 | } |
| 495 | ApplyToEachA(tgt => Controlled X(ctls, tgt), qs); |
| 496 | within { |
| 497 | ApplyToEachA(tgt => Controlled X(ctls, tgt), ys); |
| 498 | } apply { |
| 499 | Adjoint backwardAdder(xs, ys, qs); |
| 500 | } |
| 501 | } |
| 502 | controlled adjoint (ctls, ...) { |
| 503 | // When we control everything except the adders, the adders will |
| 504 | // cancel themselves. |
| 505 | let n = Length(xs); |
| 506 | |
| 507 | Fact(Length(ys) == n, "Registers xs and ys must be of same length"); |
| 508 | |
| 509 | use qs = Qubit[n]; |
| 510 | |
| 511 | within { |
| 512 | ApplyToEachA(tgt => Controlled X(ctls, tgt), ys); |
| 513 | } apply { |
| 514 | forwardAdder(xs, ys, qs); |
| 515 | } |
| 516 | ApplyToEachA(tgt => Controlled X(ctls, tgt), qs); |
| 517 | for i in IndexRange(ys) { |
| 518 | Controlled SWAP(ctls, (ys[i], qs[i])) |
| 519 | } |
| 520 | Adjoint backwardAdder(xs, ys, qs); |
| 521 | } |
| 522 | } |
| 523 | |
| 524 | // |
| 525 | // Comparisons |
| 526 | // |
| 527 | // Compare BigInt and qubit register in a little-endian format and apply action |
| 528 | // if c < x { action(target) } | ApplyIfLessL |
| 529 | // if c <= x { action(target) } | ApplyIfLessOrEqualL |
| 530 | // if c == x { action(target) } | ApplyIfEqualL |
| 531 | // if c >= x { action(target) } | ApplyIfGreaterOrEqualL |
| 532 | // if c > x { action(target) } | ApplyIfGreaterL |
| 533 | // |
| 534 | // Compare two qubit registers in a little-endian format and apply action |
| 535 | // if x < y { action(target) } | ApplyIfLessLE |
| 536 | // if x <= y { action(target) } | ApplyIfLessOrEqualLE |
| 537 | // if x == y { action(target) } | ApplyIfEqualLE |
| 538 | // if x >= y { action(target) } | ApplyIfGreaterOrEqualLE |
| 539 | // if x > y { action(target) } | ApplyIfGreaterLE |
| 540 | // |
| 541 | |
| 542 | /// # Summary |
| 543 | /// Computes `if (c < x) { action(target) }`, that is, applies `action` to `target` |
| 544 | /// if a BigInt value `c` is less than the little-endian qubit register `x` |
| 545 | operation ApplyIfLessL<'T>( |
| 546 | action : 'T => Unit is Adj + Ctl, |
| 547 | c : BigInt, |
| 548 | x : Qubit[], |
| 549 | target : 'T |
| 550 | ) : Unit is Adj + Ctl { |
| 551 | |
| 552 | ApplyActionIfGreaterThanOrEqualConstant(false, action, c + 1L, x, target); |
| 553 | } |
| 554 | |
| 555 | /// # Summary |
| 556 | /// Computes `if (c <= x) { action(target) }`, that is, applies `action` to `target` |
| 557 | /// if a BigInt value `c` is less or equal to the little-endian qubit register `x` |
| 558 | operation ApplyIfLessOrEqualL<'T>( |
| 559 | action : 'T => Unit is Adj + Ctl, |
| 560 | c : BigInt, |
| 561 | x : Qubit[], |
| 562 | target : 'T |
| 563 | ) : Unit is Adj + Ctl { |
| 564 | |
| 565 | ApplyActionIfGreaterThanOrEqualConstant(false, action, c, x, target); |
| 566 | } |
| 567 | |
| 568 | /// # Summary |
| 569 | /// Computes `if (c == x) { action(target) }`, that is, applies `action` to `target` |
| 570 | /// if a BigInt value `c` is equal to the little-endian qubit register `x` |
| 571 | operation ApplyIfEqualL<'T>( |
| 572 | action : 'T => Unit is Adj + Ctl, |
| 573 | c : BigInt, |
| 574 | xs : Qubit[], |
| 575 | target : 'T |
| 576 | ) : Unit is Adj + Ctl { |
| 577 | |
| 578 | let cBitSize = BitSizeL(c); |
| 579 | let xLen = Length(xs); |
| 580 | if (cBitSize <= xLen) { |
| 581 | let bits = BigIntAsBoolArray(c, Length(xs)); |
| 582 | within { |
| 583 | ApplyPauliFromBitString(PauliX, false, bits, xs); |
| 584 | } apply { |
| 585 | Controlled ApplyAsSinglyControlled(xs, (a => action(a), target)); |
| 586 | } |
| 587 | } |
| 588 | } |
| 589 | |
| 590 | /// # Summary |
| 591 | /// Computes `if (c >= x) { action(target) }`, that is, applies `action` to `target` |
| 592 | /// if a BigInt value `c` is greater or equal to the little-endian qubit register `x` |
| 593 | operation ApplyIfGreaterOrEqualL<'T>( |
| 594 | action : 'T => Unit is Adj + Ctl, |
| 595 | c : BigInt, |
| 596 | x : Qubit[], |
| 597 | target : 'T |
| 598 | ) : Unit is Adj + Ctl { |
| 599 | |
| 600 | ApplyActionIfGreaterThanOrEqualConstant(true, action, c + 1L, x, target); |
| 601 | } |
| 602 | |
| 603 | /// # Summary |
| 604 | /// Computes `if (c > x) { action(target) }`, that is, applies `action` to `target` |
| 605 | /// if a BigInt value `c` is greater than the little-endian qubit register `x` |
| 606 | operation ApplyIfGreaterL<'T>( |
| 607 | action : 'T => Unit is Adj + Ctl, |
| 608 | c : BigInt, |
| 609 | x : Qubit[], |
| 610 | target : 'T |
| 611 | ) : Unit is Adj + Ctl { |
| 612 | |
| 613 | ApplyActionIfGreaterThanOrEqualConstant(true, action, c, x, target); |
| 614 | } |
| 615 | |
| 616 | /// # Summary |
| 617 | /// Computes `if x < y { action(target) }`, that is, applies `action` to `target` |
| 618 | /// if register `x` is less than the register `y`. |
| 619 | /// Both qubit registers should be in a little-endian format. |
| 620 | operation ApplyIfLessLE<'T>( |
| 621 | action : 'T => Unit is Adj + Ctl, |
| 622 | x : Qubit[], |
| 623 | y : Qubit[], |
| 624 | target : 'T |
| 625 | ) : Unit is Adj + Ctl { |
| 626 | |
| 627 | ApplyIfGreaterLE(action, y, x, target); |
| 628 | } |
| 629 | |
| 630 | /// # Summary |
| 631 | /// Computes `if x <= y { action(target) }`, that is, applies `action` to `target` |
| 632 | /// if register `x` is less or equal to the register `y`. |
| 633 | /// Both qubit registers should be in a little-endian format. |
| 634 | operation ApplyIfLessOrEqualLE<'T>( |
| 635 | action : 'T => Unit is Adj + Ctl, |
| 636 | x : Qubit[], |
| 637 | y : Qubit[], |
| 638 | target : 'T |
| 639 | ) : Unit is Adj + Ctl { |
| 640 | |
| 641 | Fact(Length(x) > 0, "Bitwidth must be at least 1"); |
| 642 | within { |
| 643 | ApplyToEachA(X, x); |
| 644 | } apply { |
| 645 | // control is not inverted |
| 646 | ApplyActionIfSumOverflows(action, x, y, false, target); |
| 647 | } |
| 648 | } |
| 649 | |
| 650 | /// # Summary |
| 651 | /// Computes `if x == y { action(target) }`, that is, applies `action` to `target` |
| 652 | /// if register `x` is equal to the register `y`. |
| 653 | /// Both qubit registers should be in a little-endian format. |
| 654 | operation ApplyIfEqualLE<'T>( |
| 655 | action : 'T => Unit is Adj + Ctl, |
| 656 | x : Qubit[], |
| 657 | y : Qubit[], |
| 658 | target : 'T |
| 659 | ) : Unit is Adj + Ctl { |
| 660 | |
| 661 | Fact(Length(x) == Length(y), "x and y must be of same length"); |
| 662 | within { |
| 663 | for i in IndexRange(x) { |
| 664 | CNOT(x[i], y[i]); |
| 665 | X(y[i]); |
| 666 | } |
| 667 | } apply { |
| 668 | Controlled ApplyAsSinglyControlled(y, (a => action(a), target)) |
| 669 | } |
| 670 | } |
| 671 | |
| 672 | /// # Summary |
| 673 | /// Computes `if x >= y { action(target) }`, that is, applies `action` to `target` |
| 674 | /// if register `x` is greater or equal to the register `y`. |
| 675 | /// Both qubit registers should be in a little-endian format. |
| 676 | operation ApplyIfGreaterOrEqualLE<'T>( |
| 677 | action : 'T => Unit is Adj + Ctl, |
| 678 | x : Qubit[], |
| 679 | y : Qubit[], |
| 680 | target : 'T |
| 681 | ) : Unit is Adj + Ctl { |
| 682 | |
| 683 | ApplyIfLessOrEqualLE(action, y, x, target); |
| 684 | } |
| 685 | |
| 686 | /// # Summary |
| 687 | /// Computes `if x > y { action(target) }`, that is, applies `action` to `target` |
| 688 | /// if register `x` is greater than the register `y`. |
| 689 | /// Both qubit registers should be in a little-endian format. |
| 690 | operation ApplyIfGreaterLE<'T>( |
| 691 | action : 'T => Unit is Adj + Ctl, |
| 692 | x : Qubit[], |
| 693 | y : Qubit[], |
| 694 | target : 'T |
| 695 | ) : Unit is Adj + Ctl { |
| 696 | |
| 697 | Fact(Length(x) > 0, "Bitwidth must be at least 1"); |
| 698 | within { |
| 699 | ApplyToEachA(X, x); |
| 700 | } apply { |
| 701 | // control is inverted |
| 702 | ApplyActionIfSumOverflows(action, x, y, true, target); |
| 703 | } |
| 704 | } |
| 705 | |
| 706 | export |
| 707 | AddLE, |
| 708 | ApplyIfEqualLE, |
| 709 | ApplyIfEqualL, |
| 710 | ApplyIfGreaterLE, |
| 711 | ApplyIfGreaterL, |
| 712 | ApplyIfGreaterOrEqualLE, |
| 713 | ApplyIfGreaterOrEqualL, |
| 714 | ApplyIfLessLE, |
| 715 | ApplyIfLessL, |
| 716 | ApplyIfLessOrEqualLE, |
| 717 | ApplyIfLessOrEqualL, |
| 718 | IncByI, |
| 719 | IncByIUsingIncByLE, |
| 720 | IncByL, |
| 721 | IncByLUsingIncByLE, |
| 722 | IncByLE, |
| 723 | IncByLEUsingAddLE, |
| 724 | LookAheadDKRSAddLE, |
| 725 | MAJ, |
| 726 | ReflectAboutInteger, |
| 727 | RippleCarryCGAddLE, |
| 728 | RippleCarryCGIncByLE, |
| 729 | RippleCarryTTKIncByLE, |
| 730 | FourierTDIncByLE; |
| 731 | |