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

193lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4import Std.Diagnostics.*;
5import Std.Arrays.*;
6import Std.Math.*;
7import Std.Convert.*;
8
9import PowerProducts.*;
10import Utils.*;
11
12/// # Summary
13/// Implements phaseup operation using power products without address split.
14operation PhaseLookupViaPP(address : Qubit[], data : Bool[]) : Unit {
15 let data_length = Length(data);
16 let address_size = Length(address);
17 let addressable_space = 1 <<< address_size;
18 let data = if (addressable_space < data_length) {
19 data[...addressable_space-1]
20 } elif (addressable_space > data_length) {
21 Padded(-addressable_space, false, data)
22 } else {
23 data
24 };
25 use aux_qubits = Qubit[GetAuxCountForPP(address_size)];
26 // Transform data from minterm coefficients to polynomial coefficients.
27 let corrections = FastMobiusTransform(data);
28 let products = ConstructPowerProducts(address, aux_qubits);
29 ApplyPhasingViaZ(products, corrections);
30 DestructPowerProducts(products);
31}
32
33operation ApplyPhasingViaZ(qs : Qubit[], mask : Bool[]) : Unit {
34 Fact(Length(mask) > 0, "Mask must be a non-empty array.");
35 Fact(Length(mask) == Length(qs) + 1, "Mask row count must match qs length.");
36
37 // Ignore the first element of mask, it affects the global phase.
38 ApplyPauliFromBitString(PauliZ, true, Std.Arrays.Rest(mask), qs);
39}
40
41/// # Summary
42/// Invert phases of `qs` basis states according to the provided boolean array.
43/// If `data[i]` is `true`, the phase of |i⟩ gets is inverted (multiplied by -1).
44/// Qubit register `qs` is expected to be in little-endian order.
45///
46/// # Description
47/// This operation implements phase lookup using power products and address split.
48/// It is a Q# implementation of the "phaseup" operation from the referenced paper.
49/// This operation assumes that `Length(data)` matches `2^Length(qs)`.
50///
51/// # Input
52/// ## qs
53/// Qubit register whose basis states will have their phases inverted.
54///
55/// ## data
56/// Boolean array indicating which basis states to invert. If `data[i]` is `true`,
57/// the phase of |i⟩ gets inverted (multiplied by -1).
58///
59/// # Reference
60/// 1. [arXiv:2505.15917](https://arxiv.org/abs/2505.15917)
61/// "How to factor 2048 bit RSA integers with less than a million noisy qubits"
62/// by Craig Gidney, May 2025. Section A.3.
63operation PhaseLookupViaSplitPP(address : Qubit[], data : Bool[]) : Unit {
64 let data_length = Length(data);
65 let address_size = Length(address);
66 let addressable_space = 1 <<< address_size;
67 let data = if (addressable_space < data_length) {
68 data[...addressable_space-1]
69 } elif (addressable_space > data_length) {
70 Padded(-addressable_space, false, data)
71 } else {
72 data
73 };
74
75 Fact(address_size >= 1, "Qubit register must be at least 1.");
76 Fact(Length(data) == addressable_space, "Data length must match 2^Length(qs).");
77 let n1 = address_size >>> 1; // Number of qubits in the first half
78 let n2 = address_size - n1; // Number of qubits in the second half
79 let address_low = address[...n1-1]; // Note that address_low will be empty if n == 1
80 let address_high = address[n1...];
81 let m1 = 1 <<< n1;
82 let m2 = 1 <<< n2;
83 Fact(m1 * m2 == addressable_space, "Length of halves must match total length.");
84
85 // Allocate auxiliary qubits.
86 use aux_qubits1 = Qubit[GetAuxCountForPP(n1)];
87 use aux_qubits2 = Qubit[GetAuxCountForPP(n2)];
88
89 // Construct power products for both halves.
90 let products1 = ConstructPowerProducts(address_low, aux_qubits1);
91 let products2 = ConstructPowerProducts(address_high, aux_qubits2);
92
93 // Convert data from minterm to monomial basis using Fast Möbius Transform.
94 // and chunk it into a matrix
95 let mask_as_matrix = Chunks(m1, FastMobiusTransform(data));
96
97 // Apply phasing within each half and between halves.
98 ApplyPhasingViaZandCZ(products1, products2, mask_as_matrix);
99
100 // Undo power products of both halves.
101 DestructPowerProducts(products1);
102 DestructPowerProducts(products2);
103}
104
105/// # Summary
106/// Applies phase corrections using Z and CZ gates based on power product coefficients.
107/// This is the core quantum operation in the address-split phase lookup algorithm.
108///
109/// # Description
110/// This operation applies conditional phase flips based on a 2D mask that represents
111/// power product coefficients after Fast Möbius Transform. The algorithm treats the
112/// input qubits as split into two halves, with separate power products for each half.
113///
114/// The phase correction is applied as follows:
115/// 1. Apply Z gates to products2 based on products1[0] (for products from first half only).
116/// 2. Apply Z gates to products1 based on products2[0] (for products from second half only).
117/// 3. Apply CZ gates between corresponding products from both halves.
118///
119/// # Input
120/// ## products1
121/// Power product qubits from the first half of the address register.
122///
123/// ## products2
124/// Power product qubits from the second half of the address register.
125///
126/// ## mask
127/// 2D boolean array containing power product coefficients.
128/// - `mask[i][j]` indicates whether to apply phase correction for the product
129/// of subset i from second half and subset j from first half.
130///
131/// # Remarks
132/// The mask is obtained by applying Fast Möbius Transform to phase data
133/// and reshaping into a 2D matrix. This allows efficient quantum evaluation of
134/// the phase function using O(2^(n/2)) quantum resources instead of O(2^n).
135operation ApplyPhasingViaZandCZ(products1 : Qubit[], products2 : Qubit[], mask : Bool[][]) : Unit {
136 Fact(Length(mask) > 0, "Mask must be a non-empty array.");
137 Fact(Length(mask) == Length(products2) + 1, "Mask row count must match products2 length.");
138 Fact(Length(mask[0]) == Length(products1) + 1, "Mask column count must match products1 length.");
139
140 // ColumnAt(0, mask) doesn't correspond to any qubits from the first half,
141 // so we can apply Z (rather than CZ) based on mask values.
142 ApplyPauliFromBitString(PauliZ, true, Rest(ColumnAt(0, mask)), products2);
143
144 // mask[0] row doesn't correspond to any qubits from the second half,
145 // so we can apply Z (rather than CZ) based on mask values.
146 ApplyPauliFromBitString(PauliZ, true, Rest(mask[0]), products1);
147
148 // From the second row on, take control from the first half and apply
149 // masked multi-target CZ gates via Controlled ApplyPauliFromBitString.
150 for row in IndexRange(products1) {
151 Controlled ApplyPauliFromBitString(
152 [products1[row]],
153 (PauliZ, true, Rest(ColumnAt(row + 1, mask)), products2)
154 );
155 }
156}
157
158// =============================
159// Tests
160
161@Test()
162operation TestPhaseLookupViaPPandZ() : Unit {
163 let address_size = 3;
164 let data_length = 2^address_size;
165 let data_value_count = 2^data_length;
166
167 for i in 0..data_value_count-1 {
168 let data = Std.Convert.IntAsBoolArray(i, data_length);
169 let same = CheckOperationsAreEqual(
170 address_size,
171 PhaseLookupViaPP(_, data),
172 Multicontrolled.PhaseLookupViaMCX(data, _)
173 );
174 Fact(same, $"PhaseLookupViaPPandZ must be the same as PhaseLookupViaMCX for {data}.");
175 }
176}
177
178@Test()
179operation TestPhaseLookupViaPPandCZ() : Unit {
180 let address_size = 3;
181 let data_length = 2^address_size;
182 let data_value_count = 2^data_length;
183
184 for i in 0..data_value_count-1 {
185 let data = Std.Convert.IntAsBoolArray(i, data_length);
186 let same = CheckOperationsAreEqual(
187 address_size,
188 PhaseLookupViaSplitPP(_, data),
189 Multicontrolled.PhaseLookupViaMCX(data, _)
190 );
191 Fact(same, $"PhaseLookupViaPPandCZ must be the same as PhaseLookupViaMCX for {data}.");
192 }
193}
194