GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
513f6a768700f0bad2c5e68225186ad0f5b94728

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/RecursiveSelect.qs

368lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4import Std.Arrays.*;
5import Std.Diagnostics.*;
6import Std.Math.*;
7import Std.Convert.*;
8
9
10/// # Summary
11/// Performs table lookup using a SELECT network respecting longer addresses.
12///
13/// # Description
14/// Assuming a zero-initialized `target` register, this operation will
15/// initialize it with the bitstrings in `data` at indices according to the
16/// computational values of the `address` register.
17/// The implementation of the SELECT network is based on unary encoding as
18/// presented in [1]. The recursive implementation differs from the one
19/// presented in [2] by allowing addresses beyond the length of `data`.
20///
21/// # Input
22/// ## data
23/// The classical table lookup data which is prepared in `target` with
24/// respect to the state in `address`. Each entry in data must have
25/// the same length that must be equal to the length of `target`.
26/// ## address
27/// Address register
28/// ## target
29/// Zero-initialized target register
30///
31/// # References
32/// 1. [arXiv:1805.03662](https://arxiv.org/abs/1805.03662)
33/// "Encoding Electronic Spectra in Quantum Circuits with Linear T
34/// Complexity", Section A.
35/// 2. [arXiv:2211.01133](https://arxiv.org/abs/2211.01133)
36/// "Space-time optimized table lookup", Section 2.
37operation RecursiveLookup(
38 useAnd : Bool,
39 data : Bool[][],
40 address : Qubit[],
41 target : Qubit[]
42) : Unit {
43 let data_length = Length(data);
44 if data_length == 0 {
45 return ();
46 }
47 let address_size = Length(address);
48 if address_size == 0 {
49 ApplyPauliFromBitString(PauliX, true, data[0], target);
50 return ();
51 }
52 let addressable_space = 1 <<< address_size;
53 let data_length = MinI(data_length, addressable_space);
54 let data = data[...data_length - 1];
55 let highest_address_qubit = Tail(address);
56 let lower_address_qubits = Most(address);
57 let parts = Partitioned([MinI(addressable_space / 2, data_length)], data);
58
59 within {
60 X(highest_address_qubit);
61 } apply {
62 ControlledRecursiveSelect(useAnd, highest_address_qubit, parts[0], lower_address_qubits, target);
63 }
64 ControlledRecursiveSelect(useAnd, highest_address_qubit, parts[1], lower_address_qubits, target);
65}
66
67/// # Summary
68/// Performs table lookup using a SELECT network assuming no addresses beyond data length.
69operation RecursiveLookupOpt(
70 useAnd : Bool,
71 data : Bool[][],
72 address : Qubit[],
73 target : Qubit[]
74) : Unit {
75 let data_length = Length(data);
76 if data_length == 0 {
77 // If there's no data, there's nothing to apply.
78 return ();
79 }
80 if data_length == 1 {
81 // Base case: always apply data value if data length is 1.
82 // This version doesn't support address values beyond data length and some value needs to be applied.
83 // Since this is the only data value, it is the one to be applied.
84 ApplyPauliFromBitString(PauliX, true, data[0], target);
85 return ();
86 }
87 let addressable_space = 1 <<< Length(address);
88 if addressable_space == 1 {
89 return ();
90 }
91
92 let data_length = MinI(data_length, addressable_space);
93 let data = data[...data_length - 1];
94 let address_size_needed = BitSizeI(data_length - 1);
95 let (lower_address_qubits, highest_address_qubit) = MostAndTail(address[...address_size_needed - 1]);
96 let parts = Partitioned([2^(address_size_needed - 1)], data);
97
98 within {
99 X(highest_address_qubit);
100 } apply {
101 ControlledRecursiveSelectOpt(useAnd, highest_address_qubit, parts[0], lower_address_qubits, target);
102 }
103 ControlledRecursiveSelectOpt(useAnd, highest_address_qubit, parts[1], lower_address_qubits, target);
104}
105
106// Complete version of recursive select network that ignores address values
107// beyond data length. This is equivalent to padding data with false values
108// to cover the entire addressable space.
109// If data length is 1, single data value is used only if address is zero.
110operation ControlledRecursiveSelect(
111 useAnd : Bool,
112 control : Qubit,
113 data : Bool[][],
114 address : Qubit[],
115 target : Qubit[]
116) : Unit {
117 let data_length = Length(data);
118 if (data_length == 0) {
119 // If there's no data, there's nothing to do.
120 return ();
121 }
122
123 let address_size = Length(address);
124 if address_size == 0 {
125 // Base case. Use CX on qubits where data is true.
126 Fact(data_length == 1, "Data length must be 1 when address size is 0.");
127 Controlled ApplyPauliFromBitString([control], (PauliX, true, data[0], target));
128 return ();
129 }
130
131 let address_space = 1 <<< address_size;
132 Fact(data_length <= address_space, "Data length must not exceed addressable space.");
133
134 let highest_address_qubit = Tail(address);
135 let lower_address_qubits = Most(address);
136 let data_parts = Partitioned([address_space / 2], data);
137
138 use aux = Qubit();
139 within {
140 X(highest_address_qubit);
141 } apply {
142 if useAnd {
143 AND(control, highest_address_qubit, aux);
144 } else {
145 CCNOT(control, highest_address_qubit, aux);
146 }
147 }
148 ControlledRecursiveSelect(useAnd, aux, data_parts[0], lower_address_qubits, target);
149 CNOT(control, aux);
150 ControlledRecursiveSelect(useAnd, aux, data_parts[1], lower_address_qubits, target);
151 if useAnd {
152 Adjoint AND(control, highest_address_qubit, aux);
153 } else {
154 Adjoint CCNOT(control, highest_address_qubit, aux);
155 }
156}
157
158// Optimized version of recursive select network that expects all address values
159// to be within data length. If address value exceeds data length, behavior is undefined.
160// If data length is 1, single data value is always used.
161operation ControlledRecursiveSelectOpt(
162 useAnd : Bool,
163 control : Qubit,
164 data : Bool[][],
165 address : Qubit[],
166 target : Qubit[]
167) : Unit {
168 let data_length = Length(data);
169 Fact(data_length > 0, "ControlledRecursiveSelectOpt: Data cannot be empty.");
170
171 let address_size_needed = BitSizeI(data_length - 1);
172 Fact(Length(address) >= address_size_needed, "ControlledRecursiveSelectOpt: Address register is too short.");
173
174 if data_length == 1 {
175 // Base case: always apply data value if data length is 1.
176 Controlled ApplyPauliFromBitString([control], (PauliX, true, data[0], target));
177 } else {
178 use helper = Qubit();
179
180 // Get just enough address qubits to address all data and split data.
181 let (lower_address_qubits, highest_address_qubit) = MostAndTail(address[...address_size_needed - 1]);
182 let parts = Partitioned([1 <<< (address_size_needed - 1)], data);
183
184 within {
185 X(highest_address_qubit);
186 } apply {
187 if useAnd {
188 AND(control, highest_address_qubit, helper);
189 } else {
190 CCNOT(control, highest_address_qubit, helper);
191 }
192 }
193 ControlledRecursiveSelectOpt(useAnd, helper, parts[0], lower_address_qubits, target);
194 CNOT(control, helper);
195 ControlledRecursiveSelectOpt(useAnd, helper, parts[1], lower_address_qubits, target);
196 if useAnd {
197 Adjoint AND(control, highest_address_qubit, helper);
198 } else {
199 Adjoint CCNOT(control, highest_address_qubit, helper);
200 }
201 }
202}
203
204// =============================
205// Tests
206
207@Test()
208operation CheckRecursiveLookup() : Unit {
209 let n = 3;
210 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]];
211
212 use addr = Qubit[n];
213 use target = Qubit[3];
214
215 // Check that data at all indices is looked up correctly.
216 for i in IndexRange(data) {
217 ApplyXorInPlace(i, addr);
218 RecursiveLookup(true, data, addr, target);
219
220 ApplyPauliFromBitString(PauliX, true, data[i], target);
221 let zero = CheckAllZero(target);
222 Fact(zero, $"Target should match {data[i]} at index {i}.");
223 ResetAll(addr);
224 }
225}
226
227@Test()
228operation CheckRecursiveLookupOpt() : Unit {
229 let n = 3;
230 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]];
231
232 use addr = Qubit[n];
233 use target = Qubit[3];
234
235 // Check that data at all indices is looked up correctly.
236 for i in IndexRange(data) {
237 ApplyXorInPlace(i, addr);
238 RecursiveLookupOpt(true, data, addr, target);
239
240 ApplyPauliFromBitString(PauliX, true, data[i], target);
241 let zero = CheckAllZero(target);
242 Fact(zero, $"Target should match {data[i]} at index {i}.");
243 ResetAll(addr);
244 }
245}
246
247@Test()
248operation CheckRecursiveLookupShorterData() : Unit {
249 let n = 3;
250 let width = 3;
251 let data = [[true, false, false], [false, true, false], [false, false, true]];
252
253 use addr = Qubit[n];
254 use target = Qubit[width];
255
256 // Check that shorter data at all indices is looked up correctly.
257 // This works for all addresses even beyond data length.
258 for i in 0..2^n-1 {
259 ApplyXorInPlace(i, addr);
260 RecursiveLookup(true, data, addr, target);
261
262 mutable expected_data = [false, false, false];
263 if i < Length(data) {
264 ApplyPauliFromBitString(PauliX, true, data[i], target);
265 set expected_data = data[i];
266 } else {
267 // For out-of-bounds indices, target should remain |0...0⟩.
268 }
269 let zero = CheckAllZero(target);
270 Fact(zero, $"Target should match {expected_data} at index {i}.");
271 ResetAll(addr);
272 }
273}
274
275@Test()
276operation CheckRecursiveLookupShorterDataOpt() : Unit {
277 let n = 3;
278 let width = 3;
279 let data = [[true, false, false], [false, true, false], [false, false, true]];
280
281 use addr = Qubit[n];
282 use target = Qubit[width];
283
284 // Check that shorter data at all indices is looked up correctly.
285 // This only works up to data length.
286 for i in IndexRange(data) {
287 ApplyXorInPlace(i, addr);
288 RecursiveLookupOpt(true, data, addr, target);
289
290 ApplyPauliFromBitString(PauliX, true, data[i], target);
291 let expected_data = data[i];
292 let zero = CheckAllZero(target);
293 Fact(zero, $"Target should match {expected_data} at index {i}.");
294 ResetAll(addr);
295 }
296}
297
298@Test()
299operation CheckRecursiveLookupLongerData() : Unit {
300 let n = 2;
301 let width = 3;
302 let data = [[true, false, false], [false, true, false], [false, false, true], [false, false, false], [true, true, false], [false, true, true], [true, true, true]];
303
304 use addr = Qubit[n];
305 use target = Qubit[width];
306
307 // Check that longer data at all available indices is looked up correctly.
308 for i in 0..2^n-1 {
309 ApplyXorInPlace(i, addr);
310 RecursiveLookup(true, data, addr, target);
311
312 ApplyPauliFromBitString(PauliX, true, data[i], target);
313 let zero = CheckAllZero(target);
314 Fact(zero, $"Target should match {data[i]} at index {i}.");
315 ResetAll(addr);
316 }
317}
318
319@Test()
320operation CheckRecursiveLookupLongerDataOpt() : Unit {
321 let n = 2;
322 let width = 3;
323 let data = [[true, false, false], [false, true, false], [false, false, true], [false, false, false], [true, true, false], [false, true, true], [true, true, true]];
324
325 use addr = Qubit[n];
326 use target = Qubit[width];
327
328 // Check that longer data at all available indices is looked up correctly.
329 for i in 0..2^n-1 {
330 ApplyXorInPlace(i, addr);
331 RecursiveLookupOpt(true, data, addr, target);
332
333 ApplyPauliFromBitString(PauliX, true, data[i], target);
334 let zero = CheckAllZero(target);
335 Fact(zero, $"Target should match {data[i]} at index {i}.");
336 ResetAll(addr);
337 }
338}
339
340@Test()
341operation TestRecursiveLookupMatchesStd() : Unit {
342 let n = 3;
343 let width = 4;
344 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]];
345
346 // Use adjoint Std.TableLookup.Select because this check takes adjoint of that.
347 let equal = CheckOperationsAreEqual(
348 n + width,
349 qs => RecursiveLookup(true, data, qs[0..n-1], qs[n...]),
350 qs => Adjoint Std.TableLookup.Select(data, qs[0..n-1], qs[n...])
351 );
352 Fact(equal, "RecursiveLookup should match Std.TableLookup.Select.");
353}
354
355@Test()
356operation TestRecursiveLookupMatchesStdOpt() : Unit {
357 let n = 3;
358 let width = 4;
359 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]];
360
361 // Use adjoint Std.TableLookup.Select because this check takes adjoint of that.
362 let equal = CheckOperationsAreEqual(
363 n + width,
364 qs => RecursiveLookupOpt(true, data, qs[0..n-1], qs[n...]),
365 qs => Adjoint Std.TableLookup.Select(data, qs[0..n-1], qs[n...])
366 );
367 Fact(equal, "RecursiveLookupOpt should match Std.TableLookup.Select.");
368}
369