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

292lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4import Std.Arrays.*;
5
6import Utils.*;
7import Multicontrolled.*;
8import RecursiveSelect.*;
9import LookupViaPP.*;
10import PhaseLookup.*;
11
12// ----------------------------------------------
13// Lookup algorithm options.
14
15/// Use lookup algorithm defined in the standard library.
16function DoStdLookup() : Int {
17 0
18}
19
20/// Use basic lookup algorithm with multicontrolled X gates.
21function DoMCXLookup() : Int {
22 1
23}
24
25/// Use recursive SELECT network as lookup algorithm.
26function DoRecursiveSelectLookup() : Int {
27 2
28}
29
30/// Use lookup algorithm via power products without address split.
31function DoPPLookup() : Int {
32 3
33}
34
35/// Use lookup algorithm via power products with address split.
36function DoSplitPPLookup() : Int {
37 4
38}
39
40// ----------------------------------------------
41// Unlookup algorithm options.
42
43/// Use unlookup algorithm defined in the standard library.
44function DoStdUnlookup() : Int {
45 0
46}
47
48/// Use the same unlookup algorithm as lookup.
49/// This is always possible as lookup is self-adjoint.
50function DoUnlookupViaLookup() : Int {
51 1
52}
53
54/// Use unlookup algorithm with multicontrolled X gates.
55/// This options is measurement based and returns target to zero state.
56function DoMCXUnlookup() : Int {
57 2
58}
59
60/// Use unlookup algorithm via power products without address split (Phase lookup).
61/// This options is measurement based and returns target to zero state.
62function DoPPUnlookup() : Int {
63 3
64}
65
66/// Use unlookup algorithm via power products with address split (Phase lookup).
67/// This options is measurement based and returns target to zero state.
68function DoSplitPPUnlookup() : Int {
69 4
70}
71
72/// # Summary
73/// Options for table lookup and unlookup operations.
74struct LookupOptions {
75 // Specifies lookup algorithm. Options:
76 // `DoStdLookup`, `DoMCXLookup`, `DoRecursiveSelectLookup`, `DoPPLookup`, `DoSplitPPLookup`.
77 lookupAlgorithm : Int,
78
79 // Specifies unlookup algorithm. Options:
80 // `DoStdUnlookup`, `DoUnlookupViaLookup`, `DoMCXUnlookup`, `DoPPUnlookup`, `DoSplitPPUnlookup`.
81 unlookupAlgorithm : Int,
82 // Suggests using measurement-based uncomputation where applicable.
83 // Note that some algorithms are measurement-based only and some cannot use measurements.
84 // If `true`, use measurement-based uncomputations. Example: prefer adjoint AND.
85 // If `false`, avoid measurement-based uncomputations. Example: prefer adjoint CCNOT.
86 preferMeasurementBasedUncomputation : Bool,
87
88 // If `true`, an error is raised if data is longer than addressable space.
89 // If `false`, longer data beyond addressable space is ignored.
90 failOnLongData : Bool,
91
92 // If `true`, an error is raised if data is shorter than addressable space.
93 // If `false`, shorter data is tolerated according to respectExcessiveAddress.
94 failOnShortData : Bool,
95
96 // If `true`, all address qubits are respected and used.
97 // Addressing beyond data length yields the same result as if the data was padded with `false` values.
98 // If `false`, addressing beyond data length yields undefined results.
99 // As one consequence, when data is shorter than addressable space, higher address qubits are ignored.
100 respectExcessiveAddress : Bool,
101}
102
103/// # Summary
104/// Default lookup options. Use power products with register split for lookup and unlookup.
105function DefaultLookupOptions() : LookupOptions {
106 new LookupOptions {
107 lookupAlgorithm = DoSplitPPLookup(),
108 unlookupAlgorithm = DoSplitPPUnlookup(),
109 failOnLongData = false,
110 failOnShortData = false,
111 respectExcessiveAddress = false,
112 preferMeasurementBasedUncomputation = true,
113 }
114}
115
116/// # Summary
117/// Performs table lookup/unlookup operation using specified algorithm and other options.
118///
119/// # Input
120/// ## options
121/// LookupOptions defining lookup and unlookup algorithms and other parameters.
122/// ## data
123/// The data table to be looked up. Each entry is a Bool array the size of the target register.
124/// ## address
125/// Qubit register representing the address in little-endian format.
126/// If the state of this register is one of the basis states |i⟩, and the target register is in |0⟩,
127/// the target register will be set to the value data[i] during lookup. Address can also be in superposition.
128/// ## target
129/// Qubit register to accept the target data. Must be in the |0⟩ state for some algorithms.
130/// For specifics see the corresponding algorithm implementation.
131operation Lookup(
132 options : LookupOptions,
133 data : Bool[][],
134 address : Qubit[],
135 target : Qubit[]
136) : Unit is Adj + Ctl {
137 body (...) {
138 if (options.lookupAlgorithm == DoStdLookup()) {
139 // Don't do anything beyond standard library select.
140 Std.TableLookup.Select(data, address, target);
141 return ();
142 }
143
144 let input = PrepareAddressAndData(options, address, data);
145
146 if options.lookupAlgorithm == DoMCXLookup() {
147 // Basic lookup via multicontrolled X gates.
148 LookupViaMCX(input.fitData, input.fitAddress, target);
149 return ();
150 }
151
152 if options.lookupAlgorithm == DoRecursiveSelectLookup() {
153 // Recursive select implementation.
154 if (options.respectExcessiveAddress) {
155 RecursiveLookup(options.preferMeasurementBasedUncomputation, input.fitData, input.fitAddress, target);
156 } else {
157 RecursiveLookupOpt(options.preferMeasurementBasedUncomputation, input.fitData, input.fitAddress, target);
158 }
159 return ();
160 }
161
162 if options.lookupAlgorithm == DoPPLookup() {
163 // Lookup via power products without address split.
164 LookupViaPP(input.fitData, input.fitAddress, target);
165 return ();
166 }
167
168 if options.lookupAlgorithm == DoSplitPPLookup() {
169 LookupViaSplitPP(input.fitData, input.fitAddress, target);
170 return ();
171 }
172
173 fail $"Unknown lookup algorithm specified ({options.lookupAlgorithm}).";
174 }
175
176 controlled (controls, ...) {
177 let control_size = Length(controls);
178 if control_size == 0 {
179 Lookup(options, data, address, target);
180 return ();
181 }
182
183 if options.lookupAlgorithm == DoStdLookup() {
184 // Don't do anything beyond standard library select.
185 Controlled Std.TableLookup.Select(controls, (data, address, target));
186 return ();
187 }
188
189 let input = PrepareAddressAndData(options, address, data);
190
191 if options.lookupAlgorithm == DoMCXLookup() {
192 // This is already a multicontrolled approach. Just add more controls.
193 Controlled LookupViaMCX(controls, (data, address, target));
194 return ();
195 }
196
197 // Combine multiple controls into one.
198 use aux = Qubit[control_size - 1];
199 within {
200 CombineControls(controls, aux);
201 } apply {
202 let single_control = GetCombinedControl(controls, aux);
203
204 if options.lookupAlgorithm == DoRecursiveSelectLookup() {
205 // Recursive select implementation.
206 if (options.respectExcessiveAddress) {
207 ControlledRecursiveSelect(
208 options.preferMeasurementBasedUncomputation,
209 single_control,
210 input.fitData,
211 input.fitAddress,
212 target
213 );
214 } else {
215 ControlledRecursiveSelectOpt(
216 options.preferMeasurementBasedUncomputation,
217 single_control,
218 input.fitData,
219 input.fitAddress,
220 target
221 );
222 }
223 } else {
224 // To use control qubit as an extra address qubit we need to respect entire address.
225 // Power products implementation already does that.
226 within {
227 // Invert control so that data is selected when control is |1⟩.
228 X(single_control);
229 } apply {
230 // Add control as the most significant address qubit.
231 if options.lookupAlgorithm == DoPPLookup() {
232 LookupViaPP(input.fitData, input.fitAddress + [single_control], target);
233 } elif options.lookupAlgorithm == DoSplitPPLookup() {
234 LookupViaSplitPP(input.fitData, input.fitAddress + [single_control], target);
235 } else {
236 fail $"Unknown lookup algorithm specified ({options.lookupAlgorithm}).";
237 }
238 }
239 }
240 }
241 }
242
243 adjoint (...) {
244 if (options.unlookupAlgorithm == DoStdUnlookup()) {
245 // Don't do anything beyond standard library select.
246 Adjoint Std.TableLookup.Select(data, address, target);
247 return ();
248 }
249 if (options.unlookupAlgorithm == DoUnlookupViaLookup()) {
250 // Perform same lookup operation (as it is self-adjoint).
251 Lookup(options, data, address, target);
252 return ();
253 }
254
255 // Perform measurement-based uncomputation.
256 let input = PrepareAddressAndData(options, address, data);
257 let phaseData = MeasureAndComputePhaseData(target, input.fitData, Length(input.fitAddress));
258 // Now apply phase corrections after measurement-based uncomputation.
259
260 if options.unlookupAlgorithm == DoMCXUnlookup() {
261 // Phase lookup via multicontrolled X gates.
262 PhaseLookupViaMCX(phaseData, input.fitAddress);
263 return ();
264 }
265
266 if options.unlookupAlgorithm == DoPPUnlookup() {
267 // Phase lookup via power products without address split.
268 PhaseLookupViaPP(input.fitAddress, phaseData);
269 return ();
270 }
271
272 if options.unlookupAlgorithm == DoSplitPPUnlookup() {
273 // Phase lookup via power products with address split.
274 PhaseLookupViaSplitPP(input.fitAddress, phaseData);
275 return ();
276 }
277
278 fail $"Unknown unlookup algorithm specified ({options.unlookupAlgorithm}).";
279 }
280
281 controlled adjoint (controls, ...) {
282 if options.unlookupAlgorithm == DoStdUnlookup() {
283 // Don't do anything beyond standard library select.
284 Controlled Adjoint Std.TableLookup.Select(controls, (data, address, target));
285 return ();
286 }
287
288 // In all other cases we perform controlled lookup as
289 // we cannot do controlled measurement-based uncomputation.
290 Controlled Lookup(controls, (options, data, address, target));
291 }
292}
293