microsoft/qdk
Publicmirrored from https://github.com/microsoft/qdkAvailable
library/std/arithmetic.qs
291lines · modecode
| 1 | // Copyright (c) Microsoft Corporation. |
| 2 | // Licensed under the MIT License. |
| 3 | |
| 4 | namespace Microsoft.Quantum.Arithmetic { |
| 5 | open Microsoft.Quantum.Canon; |
| 6 | open Microsoft.Quantum.Arrays; |
| 7 | open Microsoft.Quantum.Diagnostics; |
| 8 | open Microsoft.Quantum.Measurement; |
| 9 | |
| 10 | /// # Summary |
| 11 | /// Applies a bitwise-XOR operation between a classical integer and an |
| 12 | /// integer represented by a register of qubits. |
| 13 | /// |
| 14 | /// # Description |
| 15 | /// Applies `X` operations to qubits in a little-endian register based on |
| 16 | /// 1 bits in an integer. |
| 17 | /// |
| 18 | /// Let us denote `value` by a and let y be an unsigned integer encoded in `target`, |
| 19 | /// then `ApplyXorInPlace` performs an operation given by the following map: |
| 20 | /// $\ket{y}\rightarrow \ket{y\oplus a}$ , where $\oplus$ is the bitwise exclusive OR operator. |
| 21 | operation ApplyXorInPlace(value : Int, target : Qubit[]) : Unit is Adj+Ctl { |
| 22 | body(...) { |
| 23 | Fact(value >= 0, "value must be non-negative"); |
| 24 | mutable runningValue = value; |
| 25 | for q in target { |
| 26 | if (runningValue &&& 1) != 0 { |
| 27 | X(q); |
| 28 | } |
| 29 | set runningValue >>>= 1; |
| 30 | } |
| 31 | Fact(runningValue == 0, "value is too large"); |
| 32 | } |
| 33 | adjoint self; |
| 34 | } |
| 35 | |
| 36 | /// # Summary |
| 37 | /// Measures the content of a quantum register and converts |
| 38 | /// it to an integer. The measurement is performed with respect |
| 39 | /// to the standard computational basis, i.e., the eigenbasis of `PauliZ`. |
| 40 | /// |
| 41 | /// # Input |
| 42 | /// ## target |
| 43 | /// A quantum register in the little-endian encoding. |
| 44 | /// |
| 45 | /// # Output |
| 46 | /// An unsigned integer that contains the measured value of `target`. |
| 47 | /// |
| 48 | /// # Remarks |
| 49 | /// This operation resets its input register to the |00...0> state, |
| 50 | /// suitable for releasing back to a target machine. |
| 51 | operation MeasureInteger(target: Qubit[]): Int { |
| 52 | let nBits = Length(target); |
| 53 | Fact(nBits < 64, $"`Length(target)` must be less than 64, but was {nBits}."); |
| 54 | |
| 55 | mutable number = 0; |
| 56 | for i in 0..nBits-1 { |
| 57 | if (MResetZ(target[i]) == One) { |
| 58 | set number |||= 1 <<< i; |
| 59 | } |
| 60 | } |
| 61 | |
| 62 | number |
| 63 | } |
| 64 | |
| 65 | /// # Summary |
| 66 | /// Automatically chooses between addition with |
| 67 | /// carry and without, depending on the register size of `ys`, |
| 68 | /// which holds the result after operation is complete. |
| 69 | operation AddI (xs: Qubit[], ys: Qubit[]) : Unit is Adj + Ctl { |
| 70 | if Length(xs) == Length(ys) { |
| 71 | RippleCarryAdderNoCarryTTK(xs, ys); |
| 72 | } |
| 73 | elif Length(ys) > Length(xs) { |
| 74 | use qs = Qubit[Length(ys) - Length(xs) - 1]; |
| 75 | RippleCarryAdderTTK(xs + qs, Most(ys), Tail(ys)); |
| 76 | } |
| 77 | else { |
| 78 | fail "xs must not contain more qubits than ys!"; |
| 79 | } |
| 80 | } |
| 81 | |
| 82 | /// # Summary |
| 83 | /// Reversible, in-place ripple-carry addition of two integers without carry out. |
| 84 | /// |
| 85 | /// # Description |
| 86 | /// Given two $n$-bit integers encoded in LittleEndian registers `xs` and `ys`, |
| 87 | /// the operation computes the sum of the two integers modulo $2^n$, |
| 88 | /// where $n$ is the length of the inputs arrays `xs` and `ys`, |
| 89 | /// which must be positive. It does not compute the carry out bit. |
| 90 | /// |
| 91 | /// # Input |
| 92 | /// ## xs |
| 93 | /// LittleEndian qubit register encoding the first integer summand. |
| 94 | /// ## ys |
| 95 | /// LittleEndian qubit register encoding the second integer summand, is |
| 96 | /// modified to hold the $n$ least significant bits of the sum. |
| 97 | /// |
| 98 | /// # References |
| 99 | /// - Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro: "Quantum |
| 100 | /// Addition Circuits and Unbounded Fan-Out", Quantum Information and |
| 101 | /// Computation, Vol. 10, 2010. |
| 102 | /// https://arxiv.org/abs/0910.2530 |
| 103 | /// |
| 104 | /// # Remarks |
| 105 | /// This operation has the same functionality as RippleCarryAdderTTK but does |
| 106 | /// not return the carry bit. |
| 107 | operation RippleCarryAdderNoCarryTTK(xs : Qubit[], ys : Qubit[]) |
| 108 | : Unit is Adj + Ctl { |
| 109 | Fact(Length(xs) == Length(ys), |
| 110 | "Input registers must have the same number of qubits." ); |
| 111 | Fact(Length(xs) > 0, "Array should not be empty."); |
| 112 | |
| 113 | if (Length(xs) > 1) { |
| 114 | within { |
| 115 | ApplyOuterTTKAdder(xs, ys); |
| 116 | } apply { |
| 117 | ApplyInnerTTKAdderWithoutCarry(xs, ys); |
| 118 | } |
| 119 | } |
| 120 | CNOT (xs[0], ys[0]); |
| 121 | } |
| 122 | |
| 123 | /// # Summary |
| 124 | /// Reversible, in-place ripple-carry addition of two integers. |
| 125 | /// |
| 126 | /// # Description |
| 127 | /// Given two $n$-bit integers encoded in LittleEndian registers `xs` and `ys`, |
| 128 | /// and a qubit carry, the operation computes the sum of the two integers |
| 129 | /// where the $n$ least significant bits of the result are held in `ys` and |
| 130 | /// the carry out bit is xored to the qubit `carry`. |
| 131 | /// |
| 132 | /// # Input |
| 133 | /// ## xs |
| 134 | /// LittleEndian qubit register encoding the first integer summand. |
| 135 | /// ## ys |
| 136 | /// LittleEndian qubit register encoding the second integer summand, is |
| 137 | /// modified to hold the $n$ least significant bits of the sum. |
| 138 | /// ## carry |
| 139 | /// Carry qubit, is xored with the carry out bit of the addition. |
| 140 | /// |
| 141 | /// # References |
| 142 | /// - Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro: "Quantum |
| 143 | /// Addition Circuits and Unbounded Fan-Out", Quantum Information and |
| 144 | /// Computation, Vol. 10, 2010. |
| 145 | /// https://arxiv.org/abs/0910.2530 |
| 146 | /// |
| 147 | /// # Remarks |
| 148 | /// This operation has the same functionality as RippleCarryAdderD and, |
| 149 | /// RippleCarryAdderCDKM but does not use any ancilla qubits. |
| 150 | operation RippleCarryAdderTTK(xs : Qubit[], ys : Qubit[], carry : Qubit) |
| 151 | : Unit is Adj + Ctl { |
| 152 | Fact(Length(xs) == Length(ys), |
| 153 | "Input registers must have the same number of qubits." ); |
| 154 | Fact(Length(xs) > 0, "Array should not be empty."); |
| 155 | |
| 156 | |
| 157 | if (Length(xs) > 1) { |
| 158 | CNOT(xs[Length(xs)-1], carry); |
| 159 | within { |
| 160 | ApplyOuterTTKAdder(xs, ys); |
| 161 | } apply { |
| 162 | ApplyInnerTTKAdder(xs, ys, carry); |
| 163 | } |
| 164 | } |
| 165 | else { |
| 166 | CCNOT(xs[0], ys[0], carry); |
| 167 | } |
| 168 | CNOT(xs[0], ys[0]); |
| 169 | } |
| 170 | |
| 171 | /// # Summary |
| 172 | /// Implements the outer operation for RippleCarryAdderTTK to conjugate |
| 173 | /// the inner operation to construct the full adder. Input registers |
| 174 | /// must be of the same size. |
| 175 | /// |
| 176 | /// # Input |
| 177 | /// ## xs |
| 178 | /// LittleEndian qubit register encoding the first integer summand |
| 179 | /// input to RippleCarryAdderTTK. |
| 180 | /// ## ys |
| 181 | /// LittleEndian qubit register encoding the second integer summand |
| 182 | /// input to RippleCarryAdderTTK. |
| 183 | /// |
| 184 | /// # References |
| 185 | /// - Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro: "Quantum |
| 186 | /// Addition Circuits and Unbounded Fan-Out", Quantum Information and |
| 187 | /// Computation, Vol. 10, 2010. |
| 188 | /// https://arxiv.org/abs/0910.2530 |
| 189 | internal operation ApplyOuterTTKAdder(xs : Qubit[], ys : Qubit[]) |
| 190 | : Unit is Adj + Ctl { |
| 191 | Fact(Length(xs) == Length(ys), |
| 192 | "Input registers must have the same number of qubits." ); |
| 193 | for i in 1..Length(xs)-1 { |
| 194 | CNOT(xs[i], ys[i]); |
| 195 | } |
| 196 | for i in Length(xs)-2..-1..1 { |
| 197 | CNOT(xs[i], xs[i+1]); |
| 198 | } |
| 199 | } |
| 200 | |
| 201 | /// # Summary |
| 202 | /// Implements the inner addition function for the operation |
| 203 | /// RippleCarryAdderNoCarryTTK. This is the inner operation that is conjugated |
| 204 | /// with the outer operation to construct the full adder. |
| 205 | /// |
| 206 | /// # Input |
| 207 | /// ## xs |
| 208 | /// LittleEndian qubit register encoding the first integer summand |
| 209 | /// input to RippleCarryAdderNoCarryTTK. |
| 210 | /// ## ys |
| 211 | /// LittleEndian qubit register encoding the second integer summand |
| 212 | /// input to RippleCarryAdderNoCarryTTK. |
| 213 | /// |
| 214 | /// # References |
| 215 | /// - Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro: "Quantum |
| 216 | /// Addition Circuits and Unbounded Fan-Out", Quantum Information and |
| 217 | /// Computation, Vol. 10, 2010. |
| 218 | /// https://arxiv.org/abs/0910.2530 |
| 219 | /// |
| 220 | /// # Remarks |
| 221 | /// The specified controlled operation makes use of symmetry and mutual |
| 222 | /// cancellation of operations to improve on the default implementation |
| 223 | /// that adds a control to every operation. |
| 224 | internal operation ApplyInnerTTKAdderWithoutCarry(xs : Qubit[], ys : Qubit[]) |
| 225 | : Unit is Adj + Ctl { |
| 226 | body (...) { |
| 227 | (Controlled ApplyInnerTTKAdderWithoutCarry) ([], (xs, ys)); |
| 228 | } |
| 229 | controlled ( controls, ... ) { |
| 230 | Fact(Length(xs) == Length(ys), |
| 231 | "Input registers must have the same number of qubits." ); |
| 232 | |
| 233 | for idx in 0..Length(xs) - 2 { |
| 234 | CCNOT (xs[idx], ys[idx], xs[idx + 1]); |
| 235 | } |
| 236 | for idx in Length(xs)-1..-1..1 { |
| 237 | Controlled CNOT(controls, (xs[idx], ys[idx])); |
| 238 | CCNOT(xs[idx - 1], ys[idx - 1], xs[idx]); |
| 239 | } |
| 240 | } |
| 241 | } |
| 242 | |
| 243 | /// # Summary |
| 244 | /// Implements the inner addition function for the operation |
| 245 | /// RippleCarryAdderTTK. This is the inner operation that is conjugated |
| 246 | /// with the outer operation to construct the full adder. |
| 247 | /// |
| 248 | /// # Input |
| 249 | /// ## xs |
| 250 | /// LittleEndian qubit register encoding the first integer summand |
| 251 | /// input to RippleCarryAdderTTK. |
| 252 | /// ## ys |
| 253 | /// LittleEndian qubit register encoding the second integer summand |
| 254 | /// input to RippleCarryAdderTTK. |
| 255 | /// ## carry |
| 256 | /// Carry qubit, is xored with the most significant bit of the sum. |
| 257 | /// |
| 258 | /// # References |
| 259 | /// - Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro: "Quantum |
| 260 | /// Addition Circuits and Unbounded Fan-Out", Quantum Information and |
| 261 | /// Computation, Vol. 10, 2010. |
| 262 | /// https://arxiv.org/abs/0910.2530 |
| 263 | /// |
| 264 | /// # Remarks |
| 265 | /// The specified controlled operation makes use of symmetry and mutual |
| 266 | /// cancellation of operations to improve on the default implementation |
| 267 | /// that adds a control to every operation. |
| 268 | internal operation ApplyInnerTTKAdder(xs : Qubit[], ys : Qubit[], carry : Qubit) |
| 269 | : Unit is Adj + Ctl { |
| 270 | body (...) { |
| 271 | (Controlled ApplyInnerTTKAdder)([], (xs, ys, carry)); |
| 272 | } |
| 273 | controlled ( controls, ... ) { |
| 274 | Fact(Length(xs) == Length(ys), |
| 275 | "Input registers must have the same number of qubits." ); |
| 276 | Fact(Length(xs) > 0, "Array should not be empty."); |
| 277 | |
| 278 | |
| 279 | let nQubits = Length(xs); |
| 280 | for idx in 0..nQubits - 2 { |
| 281 | CCNOT(xs[idx], ys[idx], xs[idx+1]); |
| 282 | } |
| 283 | (Controlled CCNOT)(controls, (xs[nQubits-1], ys[nQubits-1], carry)); |
| 284 | for idx in nQubits - 1..-1..1 { |
| 285 | Controlled CNOT(controls, (xs[idx], ys[idx])); |
| 286 | CCNOT(xs[idx-1], ys[idx-1], xs[idx]); |
| 287 | } |
| 288 | } |
| 289 | } |
| 290 | |
| 291 | } |