GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
iadavis/pipeline-issue-debugging

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/library/signed/src

library/signed/src/Operations.qs

331lines ยท modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation. All rights reserved.
2// Licensed under the MIT License.
3
4import Std.Arrays.Tail, Std.Arrays.Most, Std.Arrays.Enumerated;
5import Utils.AndLadder;
6import Std.Arithmetic.RippleCarryTTKIncByLE, Std.Arithmetic.ApplyIfGreaterLE;
7import Std.Diagnostics.Fact;
8
9/// # Summary
10/// Square signed integer `xs` and store
11/// the result in `result`, which must be zero initially.
12///
13/// # Input
14/// ## xs
15/// ๐‘›-bit integer to square
16/// ## result
17/// 2๐‘›-bit result, must be in state |0โŸฉ
18/// initially.
19///
20/// # Remarks
21/// The implementation relies on `SquareI`.
22operation SquareSI(xs : Qubit[], result : Qubit[]) : Unit is Adj + Ctl {
23 body (...) {
24 Controlled SquareSI([], (xs, result));
25 }
26 controlled (controls, ...) {
27 let n = Length(xs);
28 use signx = Qubit();
29 use signy = Qubit();
30
31 within {
32 CNOT(Tail(xs), signx);
33 Controlled Invert2sSI([signx], xs);
34 } apply {
35 Controlled SquareI(controls, (xs, result));
36 }
37 }
38}
39
40/// # Summary
41/// Computes the square of the integer `xs` into `result`,
42/// which must be zero initially.
43///
44/// # Input
45/// ## xs
46/// ๐‘›-bit number to square
47/// ## result
48/// 2๐‘›-bit result, must be in state |0โŸฉ initially.
49///
50/// # Remarks
51/// Uses a standard shift-and-add approach to compute the square. Saves
52/// ๐‘›-1 qubits compared to the straight-forward solution which first
53/// copies out `xs` before applying a regular multiplier and then undoing
54/// the copy operation.
55operation SquareI(xs : Qubit[], result : Qubit[]) : Unit is Adj + Ctl {
56 body (...) {
57 Controlled SquareI([], (xs, result));
58 }
59 controlled (controls, ...) {
60 let n = Length(xs);
61
62
63 let numControls = Length(controls);
64 if numControls == 0 {
65 use aux = Qubit();
66 for (idx, ctl) in Enumerated(xs) {
67 within {
68 CNOT(ctl, aux);
69 } apply {
70 Controlled RippleCarryTTKIncByLE([aux], (xs, (result[idx..idx + n])));
71 }
72 }
73 } elif numControls == 1 {
74 use aux = Qubit();
75 for (idx, ctl) in Enumerated(xs) {
76 within {
77 AND(controls[0], ctl, aux);
78 } apply {
79 Controlled RippleCarryTTKIncByLE([aux], (xs, (result[idx..idx + n])));
80 }
81 }
82 } else {
83 use aux = Qubit[numControls];
84 within {
85 AndLadder(controls, Most(aux));
86 } apply {
87 for (idx, ctl) in Enumerated(xs) {
88 within {
89 AND(Tail(Most(aux)), ctl, Tail(aux));
90 } apply {
91 Controlled RippleCarryTTKIncByLE([Tail(aux)], (xs, (result[idx..idx + n])));
92 }
93 }
94 }
95 }
96 }
97}
98
99/// # Summary
100/// Multiply integer `xs` by integer `ys` and store the result in `result`,
101/// which must be zero initially.
102///
103/// # Input
104/// ## xs
105/// ๐‘›โ‚-bit multiplicand
106/// ## ys
107/// ๐‘›โ‚‚-bit multiplier
108/// ## result
109/// (๐‘›โ‚+๐‘›โ‚‚)-bit result, must be in state |0โŸฉ initially.
110///
111/// # Remarks
112/// Uses a standard shift-and-add approach to implement the multiplication.
113/// The controlled version was improved by copying out ๐‘ฅแตข to an ancilla
114/// qubit conditioned on the control qubits, and then controlling the
115/// addition on the ancilla qubit.
116operation MultiplyI(xs : Qubit[], ys : Qubit[], result : Qubit[]) : Unit is Adj + Ctl {
117 body (...) {
118 let na = Length(xs);
119 let nb = Length(ys);
120
121 for (idx, actl) in Enumerated(xs) {
122 Controlled RippleCarryTTKIncByLE([actl], (ys, (result[idx..idx + nb])));
123 }
124 }
125 controlled (controls, ...) {
126 let na = Length(xs);
127 let nb = Length(ys);
128
129 // Perform various optimizations based on number of controls
130 let numControls = Length(controls);
131 if numControls == 0 {
132 MultiplyI(xs, ys, result);
133 } elif numControls == 1 {
134 use aux = Qubit();
135 for (idx, actl) in Enumerated(xs) {
136 within {
137 AND(controls[0], actl, aux);
138 } apply {
139 Controlled RippleCarryTTKIncByLE([aux], (ys, (result[idx..idx + nb])));
140 }
141 }
142 } else {
143 use helper = Qubit[numControls];
144 within {
145 AndLadder(controls, Most(helper));
146 } apply {
147 for (idx, actl) in Enumerated(xs) {
148 within {
149 AND(Tail(Most(helper)), actl, Tail(helper));
150 } apply {
151 Controlled RippleCarryTTKIncByLE([Tail(helper)], (ys, (result[idx..idx + nb])));
152 }
153 }
154 }
155 }
156 }
157}
158
159/// # Summary
160/// Multiply signed integer `xs` by signed integer `ys` and store
161/// the result in `result`, which must be zero initially.
162///
163/// # Input
164/// ## xs
165/// ๐‘›โ‚-bit multiplicand
166/// ## ys
167/// ๐‘›โ‚‚-bit multiplier
168/// ## result
169/// (๐‘›โ‚+๐‘›โ‚‚)-bit result, must be in state |0โŸฉ
170/// initially.
171operation MultiplySI(xs : Qubit[], ys : Qubit[], result : Qubit[]) : Unit is Adj + Ctl {
172 body (...) {
173 Controlled MultiplySI([], (xs, ys, result));
174 }
175 controlled (controls, ...) {
176 use signx = Qubit();
177 use signy = Qubit();
178
179 within {
180 CNOT(Tail(xs), signx);
181 CNOT(Tail(ys), signy);
182 Controlled Invert2sSI([signx], xs);
183 Controlled Invert2sSI([signy], ys);
184 } apply {
185 Controlled MultiplyI(controls, (xs, ys, result));
186 within {
187 CNOT(signx, signy);
188 } apply {
189 // No controls required since `result` will still be zero
190 // if we did not perform the multiplication above.
191 Controlled Invert2sSI([signy], result);
192 }
193 }
194 }
195}
196
197
198
199/// # Summary
200/// Implements a reversible sum gate. Given a carry-in bit encoded in
201/// qubit `carryIn` and two summand bits encoded in `summand1` and `summand2`,
202/// computes the bitwise xor of `carryIn`, `summand1` and `summand2` in the qubit
203/// `summand2`.
204///
205/// # Input
206/// ## carryIn
207/// Carry-in qubit.
208/// ## summand1
209/// First summand qubit.
210/// ## summand2
211/// Second summand qubit, is replaced with the lower bit of the sum of
212/// `summand1` and `summand2`.
213///
214/// # Remarks
215/// In contrast to the `Carry` operation, this does not compute the carry-out bit.
216operation Sum(carryIn : Qubit, summand1 : Qubit, summand2 : Qubit) : Unit is Adj + Ctl {
217 CNOT(summand1, summand2);
218 CNOT(carryIn, summand2);
219}
220
221/// # Summary
222/// Inverts a given integer modulo 2's complement.
223///
224/// # Input
225/// ## xs
226/// n-bit signed integer (SignedLittleEndian), will be inverted modulo
227/// 2's complement.
228operation Invert2sSI(xs : Qubit[]) : Unit is Adj + Ctl {
229 body (...) {
230 Controlled Invert2sSI([], xs);
231 }
232 controlled (controls, ...) {
233 ApplyToEachCA((Controlled X)(controls, _), xs);
234
235 use aux = Qubit[Length(xs)];
236 within {
237 Controlled X(controls, aux[0]);
238 } apply {
239 RippleCarryTTKIncByLE(aux, xs);
240 }
241 }
242}
243
244/// # Summary
245/// Divides two quantum integers.
246///
247/// # Description
248/// `xs` will hold the
249/// remainder `xs - floor(xs/ys) * ys` and `result` will hold
250/// `floor(xs/ys)`.
251///
252/// # Input
253/// ## xs
254/// $n$-bit dividend, will be replaced by the remainder.
255/// ## ys
256/// $n$-bit divisor
257/// ## result
258/// $n$-bit result, must be in state $\ket{0}$ initially
259/// and will be replaced by the result of the integer division.
260///
261/// # Remarks
262/// Uses a standard shift-and-subtract approach to implement the division.
263/// The controlled version is specialized such the subtraction does not
264/// require additional controls.
265operation DivideI(xs : Qubit[], ys : Qubit[], result : Qubit[]) : Unit is Adj + Ctl {
266 body (...) {
267 Controlled DivideI([], (xs, ys, result));
268 }
269 controlled (controls, ...) {
270 let n = Length(result);
271
272 Fact(n == Length(ys), "Integer division requires
273 equally-sized registers ys and result.");
274 Fact(n == Length(xs), "Integer division
275 requires an n-bit dividend registers.");
276
277 let xpadded = xs + result;
278
279 for i in (n - 1)..(-1)..0 {
280 let xtrunc = xpadded[i..i + n-1];
281 Controlled ApplyIfGreaterLE(controls, (X, ys, xtrunc, result[i]));
282 // if ys > xtrunc, we don't subtract:
283 (Controlled X)(controls, result[i]);
284 (Controlled Adjoint RippleCarryTTKIncByLE)([result[i]], (ys, xtrunc));
285 }
286 }
287}
288
289/// # Summary
290/// Computes the reciprocal 1/x for an unsigned integer x
291/// using integer division. The result, interpreted as an integer,
292/// will be `floor(2^(2*n-1) / x)`.
293///
294/// # Input
295/// ## xs
296/// n-bit unsigned integer
297/// ## result
298/// 2n-bit output, must be in $\ket{0}$ initially.
299///
300/// # Remarks
301/// For the input x=0, the output will be all-ones.
302operation ComputeReciprocalI(xs : Qubit[], result : Qubit[]) : Unit is Adj + Ctl {
303 body (...) {
304 Controlled ComputeReciprocalI([], (xs, result));
305 }
306 controlled (controls, ...) {
307 let n = Length(xs);
308 Fact(Length(result) == 2 * n, "Result register must contain 2n qubits.");
309 use lhs = Qubit[2 * n];
310 use padding = Qubit[n];
311 let paddedxs = xs + padding;
312 X(Tail(lhs)); // initialize left-hand side to 2^{2n-1}
313 // ... and divide:
314 (Controlled DivideI)(controls, (lhs, paddedxs, result));
315 // uncompute lhs
316 for i in 0..2 * n - 1 {
317 (Controlled RippleCarryTTKIncByLE)([result[i]], (paddedxs[0..2 * n-1-i], lhs[i..2 * n-1]));
318 }
319 X(Tail(lhs));
320 }
321}
322
323export
324 Sum,
325 MultiplyI,
326 MultiplySI,
327 SquareSI,
328 SquareI,
329 Invert2sSI,
330 DivideI,
331 ComputeReciprocalI;