GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
fedimser/memory-re

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/library/table_lookup/src

library/table_lookup/src/LookupViaPP.qs

320lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4import Std.Arrays.*;
5import Std.Diagnostics.*;
6
7import Utils.*;
8import PowerProducts.*;
9
10/// # Summary
11/// Performs table lookup using power products without register split.
12///
13/// # Description
14/// Table lookup is preformed using power products constructed from the address qubits.
15/// Data is processed using Fast Mobius Transform to fit power products structure.
16/// Longer data is ignored, shorter data is padded with false values.
17/// Little-endian format is used throughout.
18/// This version uses O(2^n) auxiliary qubits for n address qubits.
19///
20/// # Reference
21/// 1. [arXiv:2505.15917](https://arxiv.org/abs/2505.15917)
22/// "How to factor 2048 bit RSA integers with less than a million noisy qubits"
23/// by Craig Gidney, May 2025. Section A.4.
24operation LookupViaPP(
25 data : Bool[][],
26 address : Qubit[],
27 target : Qubit[]
28) : Unit {
29 let data_length = Length(data);
30 let address_size = Length(address);
31 let addressable_space = 1 <<< address_size;
32 let data = if (addressable_space < data_length) {
33 data[...addressable_space-1]
34 } elif (addressable_space > data_length) {
35 Padded(-addressable_space, Repeated(false, Length(target)), data)
36 } else {
37 data
38 };
39
40 // Allocate auxiliary qubits.
41 use aux_qubits = Qubit[GetAuxCountForPP(address_size)];
42
43 // Construct power products.
44 let products = ConstructPowerProducts(address, aux_qubits);
45
46 ApplyFlips(data, products, [], target);
47
48 // Undo power products.
49 DestructPowerProducts(products);
50
51}
52
53/// # Summary
54/// Performs table lookup using power products and register split.
55///
56/// # Description
57/// Table lookup is preformed using power products constructed from the address qubits.
58/// Data is processed using Fast Mobius Transform to fit power products structure.
59/// Longer data is ignored, shorter data is padded with false values.
60/// Little-endian format is used throughout. Address register is split into two halves.
61/// This version uses O(2^(n/2)) auxiliary qubits for n address qubits.
62///
63/// # Reference
64/// 1. [arXiv:2505.15917](https://arxiv.org/abs/2505.15917)
65/// "How to factor 2048 bit RSA integers with less than a million noisy qubits"
66/// by Craig Gidney, May 2025. Section A.4.
67operation LookupViaSplitPP(
68 data : Bool[][],
69 address : Qubit[],
70 target : Qubit[]
71) : Unit {
72 let data_length = Length(data);
73 let address_size = Length(address);
74 let addressable_space = 1 <<< address_size;
75 let data = if (addressable_space < data_length) {
76 data[...addressable_space-1]
77 } elif (addressable_space > data_length) {
78 Padded(-addressable_space, Repeated(false, Length(target)), data)
79 } else {
80 data
81 };
82
83 let m = 2^address_size;
84 Fact(address_size >= 1, "Qubit register must be at least 1.");
85 Fact(Length(data) == m, "Data length must match 2^Length(qs).");
86 let n1 = address_size >>> 1; // Number of qubits in the first half
87 let n2 = address_size - n1; // Number of qubits in the second half
88 let h1 = address[...n1-1]; // Note that h1 will be empty if address_size == 1
89 let h2 = address[n1...];
90 let m1 = 1 <<< n1;
91 let m2 = 1 <<< n2;
92 Fact(m1 * m2 == m, "Length of halves must match total length.");
93
94 // Allocate auxiliary qubits.
95 use aux_qubits1 = Qubit[2^n1 - n1 - 1];
96 use aux_qubits2 = Qubit[2^n2 - n2 - 1];
97
98 // Construct power products for both halves.
99 let products1 = ConstructPowerProducts(h1, aux_qubits1);
100 let products2 = ConstructPowerProducts(h2, aux_qubits2);
101
102 ApplyFlips(data, products1, products2, target);
103
104 // Undo power products of both halves.
105 DestructPowerProducts(products1);
106 DestructPowerProducts(products2);
107}
108
109/// # Summary
110/// Applies flips to the target register based on the data and power products.
111operation ApplyFlips(
112 data : Bool[][],
113 products1 : Qubit[],
114 products2 : Qubit[],
115 target : Qubit[]
116) : Unit {
117 let m1 = Length(products1) + 1;
118 let m2 = Length(products2) + 1;
119
120 for bit_index in IndexRange(target) {
121 let sourceData = Mapped(a -> a[bit_index], data);
122 let flipData = FastMobiusTransform(sourceData);
123 let mask_as_matrix = Chunks(m1, flipData);
124
125 // Apply X to target[bit_index] if the empty product (index 0) is set.
126 if mask_as_matrix[0][0] {
127 X(target[bit_index]);
128 }
129
130 for row in 0..m2-2 {
131 if (mask_as_matrix[row + 1][0]) {
132 CX(products2[row], target[bit_index]);
133 }
134 }
135
136 for col in 0..m1-2 {
137 if (mask_as_matrix[0][col + 1]) {
138 CX(products1[col], target[bit_index]);
139 }
140 }
141
142 for row in 0..m2-2 {
143 for col in 0..m1-2 {
144 if mask_as_matrix[row + 1][col + 1] {
145 CCNOT(products2[row], products1[col], target[bit_index]);
146 }
147 }
148 }
149
150 }
151}
152
153// =============================
154// Tests
155
156@Test()
157operation CheckLookupViaPP() : Unit {
158 let n = 3;
159 let data = [[true, false, false], [false, true, false], [false, false, true], [false, false, false], [true, true, false], [false, true, true], [true, false, true], [true, true, true]];
160
161 use addr = Qubit[n];
162 use target = Qubit[3];
163
164 // Check that data at all indices is looked up correctly.
165 for i in IndexRange(data) {
166 ApplyXorInPlace(i, addr);
167 LookupViaPP(data, addr, target);
168
169 ApplyPauliFromBitString(PauliX, true, data[i], target);
170 let zero = CheckAllZero(target);
171 Fact(zero, $"Target should match {data[i]} at index {i}.");
172 ResetAll(addr);
173 }
174}
175
176@Test()
177operation CheckLookupViaPPShorterData() : Unit {
178 let n = 3;
179 let width = 3;
180 let data = [[true, false, false], [false, true, false], [false, false, true]];
181
182 use addr = Qubit[n];
183 use target = Qubit[width];
184
185 // Check that shorter data at all indices is looked up correctly.
186 for i in 0..2^n-1 {
187 ApplyXorInPlace(i, addr);
188 LookupViaPP(data, addr, target);
189
190 mutable expected_data = [false, false, false];
191 if i < Length(data) {
192 ApplyPauliFromBitString(PauliX, true, data[i], target);
193 set expected_data = data[i];
194 } else {
195 // For out-of-bounds indices, target should remain |0...0⟩.
196 }
197 let zero = CheckAllZero(target);
198 Fact(zero, $"Target should match {expected_data} at index {i}.");
199 ResetAll(addr);
200 }
201}
202
203@Test()
204operation CheckLookupViaPPLongerData() : Unit {
205 let n = 2;
206 let width = 3;
207 let data = [[true, false, false], [false, true, false], [false, false, true], [false, false, false], [true, true, false], [false, true, true], [true, true, true]];
208
209 use addr = Qubit[n];
210 use target = Qubit[width];
211
212 // Check that longer data at all available indices is looked up correctly.
213 for i in 0..2^n-1 {
214 ApplyXorInPlace(i, addr);
215 LookupViaPP(data, addr, target);
216
217 ApplyPauliFromBitString(PauliX, true, data[i], target);
218 let zero = CheckAllZero(target);
219 Fact(zero, $"Target should match {data[i]} at index {i}.");
220 ResetAll(addr);
221 }
222}
223
224@Test()
225operation TestLookupViaPPMatchesStd() : Unit {
226 let n = 3;
227 let width = 4;
228 let data = [[true, false, false, false], [false, true, false, false], [false, false, true, false], [false, false, false, false], [true, true, false, false], [false, true, true, false], [true, false, true, true], [true, true, true, true]];
229
230 // Use adjoint Std.TableLookup.Select because this check takes adjoint of that.
231 let equal = CheckOperationsAreEqual(
232 n + width,
233 qs => LookupViaPP(data, qs[0..n-1], qs[n...]),
234 qs => Adjoint Std.TableLookup.Select(data, qs[0..n-1], qs[n...])
235 );
236 Fact(equal, "LookupViaPP should match Std.TableLookup.Select.");
237}
238
239@Test()
240operation CheckLookupViaSplitPP() : Unit {
241 let n = 3;
242 let data = [[true, false, false], [false, true, false], [false, false, true], [false, false, false], [true, true, false], [false, true, true], [true, false, true], [true, true, true]];
243
244 use addr = Qubit[n];
245 use target = Qubit[3];
246
247 // Check that data at all indices is looked up correctly.
248 for i in IndexRange(data) {
249 ApplyXorInPlace(i, addr);
250 LookupViaSplitPP(data, addr, target);
251
252 ApplyPauliFromBitString(PauliX, true, data[i], target);
253 let zero = CheckAllZero(target);
254 Fact(zero, $"Target should match {data[i]} at index {i}.");
255 ResetAll(addr);
256 }
257}
258
259@Test()
260operation CheckLookupViaSplitPPShorterData() : Unit {
261 let n = 3;
262 let width = 3;
263 let data = [[true, false, false], [false, true, false], [false, false, true]];
264
265 use addr = Qubit[n];
266 use target = Qubit[width];
267
268 // Check that shorter data at all indices is looked up correctly.
269 for i in 0..2^n-1 {
270 ApplyXorInPlace(i, addr);
271 LookupViaSplitPP(data, addr, target);
272
273 mutable expected_data = [false, false, false];
274 if i < Length(data) {
275 ApplyPauliFromBitString(PauliX, true, data[i], target);
276 set expected_data = data[i];
277 } else {
278 // For out-of-bounds indices, target should remain |0...0⟩.
279 }
280 let zero = CheckAllZero(target);
281 Fact(zero, $"Target should match {expected_data} at index {i}.");
282 ResetAll(addr);
283 }
284}
285
286@Test()
287operation CheckLookupViaSplitPPLongerData() : Unit {
288 let n = 2;
289 let width = 3;
290 let data = [[true, false, false], [false, true, false], [false, false, true], [false, false, false], [true, true, false], [false, true, true], [true, true, true]];
291
292 use addr = Qubit[n];
293 use target = Qubit[width];
294
295 // Check that longer data at all available indices is looked up correctly.
296 for i in 0..2^n-1 {
297 ApplyXorInPlace(i, addr);
298 LookupViaSplitPP(data, addr, target);
299
300 ApplyPauliFromBitString(PauliX, true, data[i], target);
301 let zero = CheckAllZero(target);
302 Fact(zero, $"Target should match {data[i]} at index {i}.");
303 ResetAll(addr);
304 }
305}
306
307@Test()
308operation TestLookupViaSplitPPMatchesStd() : Unit {
309 let n = 3;
310 let width = 4;
311 let data = [[true, false, false, false], [false, true, false, false], [false, false, true, false], [false, false, false, false], [true, true, false, false], [false, true, true, false], [true, false, true, true], [true, true, true, true]];
312
313 // Use adjoint Std.TableLookup.Select because this check takes adjoint of that.
314 let equal = CheckOperationsAreEqual(
315 n + width,
316 qs => LookupViaSplitPP(data, qs[0..n-1], qs[n...]),
317 qs => Adjoint Std.TableLookup.Select(data, qs[0..n-1], qs[n...])
318 );
319 Fact(equal, "LookupViaSplitPP should match Std.TableLookup.Select.");
320}
321