GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored fromhttps://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
v1.25.1

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/library/std/src/Std

library/std/src/Std/ArithmeticUtils.qs

521lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4import
5 Std.Diagnostics.Fact,
6 Std.Arrays.*,
7 Std.Math.Floor,
8 Std.Math.Lg,
9 Std.Math.HammingWeightI,
10 Std.Math.TrailingZeroCountL,
11 Std.Convert.IntAsDouble;
12
13/// # Summary
14/// Implements the outer operation for RippleCarryTTKIncByLE to conjugate
15/// the inner operation to construct the full adder. Only Length(xs)
16/// qubits are processed.
17///
18/// # Input
19/// ## xs
20/// Qubit register in a little-endian format containing the first summand
21/// input to RippleCarryTTKIncByLE.
22/// ## ys
23/// Qubit register in a little-endian format containing the second summand
24/// input to RippleCarryTTKIncByLE.
25///
26/// # References
27/// - Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro: "Quantum
28/// Addition Circuits and Unbounded Fan-Out", Quantum Information and
29/// Computation, Vol. 10, 2010.
30/// https://arxiv.org/abs/0910.2530
31operation ApplyOuterTTKAdder(xs : Qubit[], ys : Qubit[]) : Unit is Adj + Ctl {
32 Fact(Length(xs) <= Length(ys), "Input register ys must be at lease as long as xs.");
33 for i in 1..Length(xs) - 1 {
34 CNOT(xs[i], ys[i]);
35 }
36 for i in Length(xs) - 2..-1..1 {
37 CNOT(xs[i], xs[i + 1]);
38 }
39}
40
41/// # Summary
42/// Implements the inner addition function for the operation
43/// RippleCarryTTKIncByLE. This is the inner operation that is conjugated
44/// with the outer operation to construct the full adder.
45///
46/// # Input
47/// ## xs
48/// Qubit register in a little-endian format containing the first summand
49/// input to RippleCarryTTKIncByLE.
50/// ## ys
51/// Qubit register in a little-endian format containing the second summand
52/// input to RippleCarryTTKIncByLE.
53///
54/// # References
55/// - Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro: "Quantum
56/// Addition Circuits and Unbounded Fan-Out", Quantum Information and
57/// Computation, Vol. 10, 2010.
58/// https://arxiv.org/abs/0910.2530
59///
60/// # Remarks
61/// The specified controlled operation makes use of symmetry and mutual
62/// cancellation of operations to improve on the default implementation
63/// that adds a control to every operation.
64operation ApplyInnerTTKAdderNoCarry(xs : Qubit[], ys : Qubit[]) : Unit is Adj + Ctl {
65 body (...) {
66 (Controlled ApplyInnerTTKAdderNoCarry)([], (xs, ys));
67 }
68 controlled (controls, ...) {
69 Fact(Length(xs) == Length(ys), "Input registers must have the same number of qubits.");
70
71 for idx in 0..Length(xs) - 2 {
72 CCNOT(xs[idx], ys[idx], xs[idx + 1]);
73 }
74 for idx in Length(xs) - 1..-1..1 {
75 Controlled CNOT(controls, (xs[idx], ys[idx]));
76 CCNOT(xs[idx - 1], ys[idx - 1], xs[idx]);
77 }
78 }
79}
80
81/// # Summary
82/// Implements the inner addition function for the operation
83/// RippleCarryTTKIncByLE. This is the inner operation that is conjugated
84/// with the outer operation to construct the full adder.
85///
86/// # Input
87/// ## xs
88/// Qubit register in a little-endian format containing the first summand
89/// input to RippleCarryTTKIncByLE.
90/// ## ys
91/// Qubit register in a little-endian format containing the second summand
92/// input to RippleCarryTTKIncByLE.
93///
94/// # References
95/// - Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro: "Quantum
96/// Addition Circuits and Unbounded Fan-Out", Quantum Information and
97/// Computation, Vol. 10, 2010.
98/// https://arxiv.org/abs/0910.2530
99///
100/// # Remarks
101/// The specified controlled operation makes use of symmetry and mutual
102/// cancellation of operations to improve on the default implementation
103/// that adds a control to every operation.
104operation ApplyInnerTTKAdderWithCarry(xs : Qubit[], ys : Qubit[]) : Unit is Adj + Ctl {
105 body (...) {
106 (Controlled ApplyInnerTTKAdderWithCarry)([], (xs, ys));
107 }
108 controlled (controls, ...) {
109 Fact(Length(xs) + 1 == Length(ys), "ys must be one qubit longer then xs.");
110 Fact(Length(xs) > 0, "Array should not be empty.");
111
112
113 let nQubits = Length(xs);
114 for idx in 0..nQubits - 2 {
115 CCNOT(xs[idx], ys[idx], xs[idx + 1]);
116 }
117 (Controlled CCNOT)(controls, (xs[nQubits - 1], ys[nQubits - 1], ys[nQubits]));
118 for idx in nQubits - 1..-1..1 {
119 Controlled CNOT(controls, (xs[idx], ys[idx]));
120 CCNOT(xs[idx - 1], ys[idx - 1], xs[idx]);
121 }
122 }
123}
124
125/// # Summary
126/// Implements Half-adder. Adds qubit x to qubit y and sets carryOut appropriately
127operation HalfAdderForInc(x : Qubit, y : Qubit, carryOut : Qubit) : Unit is Adj + Ctl {
128 body (...) {
129 CCNOT(x, y, carryOut);
130 CNOT(x, y);
131 }
132 adjoint auto;
133
134 controlled (ctls, ...) {
135 Fact(Length(ctls) == 1, "HalfAdderForInc should be controlled by exactly one control qubit.");
136
137 let ctl = ctls[0];
138 use helper = Qubit();
139
140 within {
141 AND(x, y, helper);
142 } apply {
143 AND(ctl, helper, carryOut);
144 }
145 CCNOT(ctl, x, y);
146 }
147 controlled adjoint auto;
148}
149
150/// # Summary
151/// Implements Full-adder. Adds qubit carryIn and x to qubit y and sets carryOut appropriately.
152operation FullAdderForInc(carryIn : Qubit, x : Qubit, y : Qubit, carryOut : Qubit) : Unit is Adj + Ctl {
153 body (...) {
154 // TODO: cannot use `Carry` operation here
155 CNOT(carryIn, x);
156 CNOT(carryIn, y);
157 CCNOT(x, y, carryOut);
158 CNOT(carryIn, carryOut);
159 CNOT(carryIn, x);
160 CNOT(x, y);
161 }
162 adjoint auto;
163
164 controlled (ctls, ...) {
165 Fact(Length(ctls) == 1, "FullAdderForInc should be controlled by exactly one control qubit.");
166
167 let ctl = ctls[0];
168 use helper = Qubit();
169
170 CarryForInc(carryIn, x, y, helper);
171 CCNOT(ctl, helper, carryOut);
172 Controlled UncarryForInc(ctls, (carryIn, x, y, helper));
173 }
174 controlled adjoint auto;
175}
176
177// Computes carryOut := carryIn + x + y
178operation FullAdder(carryIn : Qubit, x : Qubit, y : Qubit, carryOut : Qubit) : Unit is Adj {
179 CNOT(x, y);
180 CNOT(x, carryIn);
181 AND(y, carryIn, carryOut);
182 CNOT(x, y);
183 CNOT(x, carryOut);
184 CNOT(y, carryIn);
185}
186
187/// # Summary
188/// Computes carry bit for a full adder.
189operation CarryForInc(carryIn : Qubit, x : Qubit, y : Qubit, carryOut : Qubit) : Unit is Adj + Ctl {
190 body (...) {
191 CNOT(carryIn, x);
192 CNOT(carryIn, y);
193 AND(x, y, carryOut);
194 CNOT(carryIn, carryOut);
195 }
196 adjoint auto;
197 controlled (ctls, ...) {
198 // This CarryForInc is intended to be used only in an in-place
199 // ripple-carry implementation. Only such particular use case allows
200 // for this simple implementation where controlled version
201 // is the same as uncontrolled body.
202 CarryForInc(carryIn, x, y, carryOut);
203 }
204 controlled adjoint auto;
205}
206
207/// # Summary
208/// Uncomputes carry bit for a full adder.
209operation UncarryForInc(carryIn : Qubit, x : Qubit, y : Qubit, carryOut : Qubit) : Unit is Adj + Ctl {
210 body (...) {
211 CNOT(carryIn, carryOut);
212 Adjoint AND(x, y, carryOut);
213 CNOT(carryIn, x);
214 CNOT(x, y);
215 }
216 adjoint auto;
217 controlled (ctls, ...) {
218 Fact(Length(ctls) == 1, "UncarryForInc should be controlled by exactly one control qubit.");
219
220 let ctl = ctls[0];
221
222 CNOT(carryIn, carryOut);
223 Adjoint AND(x, y, carryOut);
224 CCNOT(ctl, x, y); // Controlled X(ctls + [x], y);
225 CNOT(carryIn, x);
226 CNOT(carryIn, y);
227 }
228 controlled adjoint auto;
229}
230
231operation ApplyOrAssuming0Target(control1 : Qubit, control2 : Qubit, target : Qubit) : Unit is Adj {
232 within {
233 X(control1);
234 X(control2);
235 } apply {
236 AND(control1, control2, target);
237 X(target);
238 }
239}
240
241/// # Summary
242/// Computes carries for the look-ahead adder
243operation ComputeCarries(ps : Qubit[], gs : Qubit[]) : Unit is Adj {
244 let n = Length(gs);
245 Fact(Length(ps) + 1 == n, "Register gs must be one qubit longer than register ps.");
246
247 let T = Floor(Lg(IntAsDouble(n)));
248 use qs = Qubit[n - HammingWeightI(n) - T];
249
250 let registerPartition = MappedOverRange(t -> Floor(IntAsDouble(n) / IntAsDouble(2^t)) - 1, 1..T - 1);
251 let pWorkspace = [ps] + Partitioned(registerPartition, qs);
252
253 // Note that we cannot use AND gate targeting gs[0] as it may not be in the 0 state.
254 // We use regular CCNOT in GRounds and CRounds.
255 within {
256 PRounds(pWorkspace);
257 } apply {
258 // U_G
259 GRounds(pWorkspace, gs);
260
261 // U_C
262 CRounds(pWorkspace, gs);
263 }
264}
265
266/// # Summary
267/// Computes all p[i, j] values in workspace for the look-ahead adder.
268///
269/// The register array `pWorkspace` has T entries, where T = ⌊log₂ n⌋.
270///
271/// The first entry `pWorkspace[0]` is initialized with `P_0` which is
272/// computed before `ComputeCarries` is called. The other registers are
273/// 0-initialized and will be computed in successive rounds t = 1, ..., T - 1.
274///
275/// In each round t we compute
276///
277/// p[i, j] = p[2ᵗ × m, 2ᵗ × (m + 1)] = p[i, k] ∧ p[k, j]
278///
279/// in `pWorkspace[t][m - 1]` and use that for k = 2ᵗ × m + 2ᵗ⁻¹, p[i, k] and p[k, j]
280/// have already been computed in round t - 1 in `pWorkspace[t - 1][2 * m - 1]` and
281/// `pWorkspace[t - 1][2 * m]`, respectively.
282operation PRounds(pWorkspace : Qubit[][]) : Unit is Adj {
283 for ws in Windows(2, pWorkspace) {
284 // note that we are using Rest, since pWorkspace[t - 1][0] is never
285 // accessed in round t.
286 let (current, next) = (Rest(ws[0]), ws[1]);
287
288 for m in IndexRange(next) {
289 AND(current[2 * m], current[2 * m + 1], next[m]);
290 }
291 }
292}
293
294/// # Summary
295/// Computes g[i ∧ (i + 1), i + 1] into gs[i] for the look-ahead adder.
296///
297/// The register gs has n entries initialized to gs[i] = g[i, i + 1].
298///
299/// After successive rounds t = 1, ..., T, the register is updated to
300/// gs[i] = g[i ∧ (i + 1), i + 1], from which we can compute the carries
301/// in the C-rounds.
302operation GRounds(pWorkspace : Qubit[][], gs : Qubit[]) : Unit is Adj {
303 let T = Length(pWorkspace);
304 let n = Length(gs);
305
306 for t in 1..T {
307 let length = Floor(IntAsDouble(n) / IntAsDouble(2^t)) - 1;
308 let ps = pWorkspace[t - 1][0..2...];
309
310 for m in 0..length {
311 CCNOT(gs[2^t * m + 2^(t - 1) - 1], ps[m], gs[2^t * m + 2^t - 1]);
312 }
313 }
314}
315
316/// # Summary
317/// Computes carries into gs for the look-ahead adder.
318operation CRounds(pWorkspace : Qubit[][], gs : Qubit[]) : Unit is Adj {
319 let n = Length(gs);
320
321 let start = Floor(Lg(IntAsDouble(2 * n) / 3.0));
322 for t in start..-1..1 {
323 let length = Floor(IntAsDouble(n - 2^(t - 1)) / IntAsDouble(2^t));
324 let ps = pWorkspace[t - 1][1..2...];
325
326 for m in 1..length {
327 CCNOT(gs[2^t * m - 1], ps[m - 1], gs[2^t * m + 2^(t - 1) - 1]);
328 }
329 }
330}
331
332operation PhaseGradient(qs : Qubit[]) : Unit is Adj + Ctl {
333 for i in IndexRange(qs) {
334 R1Frac(1, i, qs[i]);
335 }
336}
337
338//
339// operations for comparisons
340//
341
342/// # Summary
343/// Applies `action` to `target` if register `x` is greater or equal to BigInt `c`
344/// (if `invertControl` is false). If `invertControl` is true, the `action`
345/// is applied in the opposite situation.
346operation ApplyActionIfGreaterThanOrEqualConstant<'T>(
347 invertControl : Bool,
348 action : 'T => Unit is Adj + Ctl,
349 c : BigInt,
350 x : Qubit[],
351 target : 'T
352) : Unit is Adj + Ctl {
353
354 let bitWidth = Length(x);
355 if c == 0L {
356 if not invertControl {
357 action(target);
358 }
359 } elif c >= (2L^bitWidth) {
360 if invertControl {
361 action(target);
362 }
363 } else {
364 // normalize constant
365 let l = TrailingZeroCountL(c);
366
367 let cNormalized = c >>> l;
368 let xNormalized = x[l...];
369 let bitWidthNormalized = Length(xNormalized);
370
371 // If c == 2L^(bitwidth - 1), then bitWidthNormalized will be 1,
372 // and qs will be empty. In that case, we do not need to compute
373 // any temporary values, and some optimizations are apply, which
374 // are considered in the remainder.
375 use qs = Qubit[bitWidthNormalized - 1];
376 let cs1 = IsEmpty(qs) ? [] | [Head(xNormalized)] + Most(qs);
377
378 Fact(Length(cs1) == Length(qs), "Arrays should be of the same length.");
379
380 within {
381 for i in 0..Length(cs1) - 1 {
382 let op = cNormalized &&& (1L <<< (i + 1)) != 0L ? AND | ApplyOrAssuming0Target;
383 op(cs1[i], xNormalized[i + 1], qs[i]);
384 }
385 } apply {
386 let control = IsEmpty(qs) ? Tail(x) | Tail(qs);
387 within {
388 if invertControl {
389 X(control);
390 }
391 } apply {
392 Controlled action([control], target);
393 }
394 }
395 }
396}
397
398/// # Summary
399/// Applies `action` to `target` if the sum of `x` and `y` registers
400/// overflows, i.e. there's a carry out (if `invertControl` is false).
401/// If `invertControl` is true, the `action` is applied when there's no carry out.
402operation ApplyActionIfSumOverflows<'T>(
403 action : 'T => Unit is Adj + Ctl,
404 x : Qubit[],
405 y : Qubit[],
406 invertControl : Bool,
407 target : 'T
408) : Unit is Adj + Ctl {
409
410 let n = Length(x);
411 Fact(n >= 1, "Registers must contain at least one qubit.");
412 Fact(Length(y) == n, "Registers must be of the same length.");
413
414 use carries = Qubit[n];
415
416 within {
417 CarryWith1CarryIn(x[0], y[0], carries[0]);
418 for i in 1..n - 1 {
419 CarryForInc(carries[i - 1], x[i], y[i], carries[i]);
420 }
421 } apply {
422 within {
423 if invertControl {
424 X(carries[n - 1]);
425 }
426 } apply {
427 Controlled action([carries[n - 1]], target);
428 }
429 }
430}
431
432/// # Summary
433/// Computes carry out assuming carry in is 1.
434/// Simplified version that is only applicable for scenarios
435/// where controlled version is the same as non-controlled.
436operation CarryWith1CarryIn(
437 x : Qubit,
438 y : Qubit,
439 carryOut : Qubit
440) : Unit is Adj + Ctl {
441
442 body (...) {
443 X(x);
444 X(y);
445 AND(x, y, carryOut);
446 X(carryOut);
447 }
448
449 adjoint auto;
450
451 controlled (ctls, ...) {
452 Fact(Length(ctls) <= 1, "Number of control lines must be at most 1");
453 CarryWith1CarryIn(x, y, carryOut);
454 }
455
456 controlled adjoint auto;
457}
458
459/// # Summary
460/// This wrapper allows operations that support only one control
461/// qubit to be used in a multi-controlled scenarios. It provides
462/// controlled version that collects controls into one qubit
463/// by applying AND chain using auxiliary qubit array.
464operation ApplyAsSinglyControlled<'TIn>(
465 op : ('TIn => Unit is Adj + Ctl),
466 input : 'TIn
467) : Unit is Adj + Ctl {
468
469 body (...) {
470 op(input);
471 }
472
473 controlled (ctls, ...) {
474 let n = Length(ctls);
475 if n == 0 {
476 op(input);
477 } elif n == 1 {
478 Controlled op(ctls, input);
479 } else {
480 use aux = Qubit[n - 1];
481 within {
482 LogDepthAndChain(ctls, aux);
483 } apply {
484 Controlled op([Tail(aux)], input);
485 }
486 }
487 }
488}
489
490/// # Summary
491/// This helper function computes the AND of all control bits in `ctls` into
492/// the last qubit of `tgts`, using the other qubits in `tgts` as helper
493/// qubits for the AND of subsets of control bits. The operation has a
494/// logarithmic depth of AND gates by aligning them using a balanced binary
495/// tree.
496operation LogDepthAndChain(ctls : Qubit[], tgts : Qubit[]) : Unit is Adj {
497 let lc = Length(ctls);
498 let lt = Length(tgts);
499
500 Fact(lc == lt + 1, $"There must be exactly one more control qubit than target qubits (got {lc}, {lt})");
501
502 if lt == 1 {
503 AND(ctls[0], ctls[1], tgts[0]);
504 } elif lt == 2 {
505 AND(ctls[0], ctls[1], tgts[0]);
506 AND(ctls[2], tgts[0], tgts[1]);
507 } else {
508 let left = lc / 2;
509 let right = lc - left;
510
511 let ctlsLeft = ctls[...left - 1];
512 let tgtsLeft = tgts[...left - 2];
513
514 let ctlsRight = ctls[left..left + right - 1];
515 let tgtsRight = tgts[left - 1..left + right - 3];
516
517 LogDepthAndChain(ctlsLeft, tgtsLeft);
518 LogDepthAndChain(ctlsRight, tgtsRight);
519 AND(Tail(tgtsLeft), Tail(tgtsRight), Tail(tgts));
520 }
521}
522