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