GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
swernli/eval-optimization

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

181lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4import Std.Arrays.IndexRange;
5import Std.Diagnostics.*;
6
7/// # Summary
8/// Constructs power products - AND-ed subsets of qubits from the input register `qs`.
9/// `2^Length(qs) - 1` qubits corresponding to non-empty subsets of `qs` are placed into the result array.
10///
11/// # Description
12/// Resulting subsets correspond to an integer index that runs from `1` to `(2^Length(qs))-1`.
13/// (Since the empty set (index 0) is not included in the result, actual array indexes should be shifted.)
14/// Indexes are treated as bitmasks indicating if a particular qubit is included.
15/// Bitmasks `2^i` includes only qubit `qs[i]`, which is placed into the resulting array at index 2^i - 1.
16/// Bitmasks with more than one bit set correspond to subsets with multiple qubits from `qs`.
17/// Qubits for these masks are taken from aux_qubits register and their value is set using AND gates.
18/// Note:
19/// 1. Empty set is not included in the result.
20/// 2. For sets that only contain one qubit, the input qubits are reused.
21///
22/// # Alt summary
23/// Takes a register of qubits and returns "power products" - qubits corresponding to all non-empty subsets
24/// of the qubits from the input register: each power product qubit state is a result of AND operation
25/// for the qubits in corresponding subset.
26operation ConstructPowerProducts(qubits : Qubit[], aux_qubits : Qubit[]) : Qubit[] {
27 // Start with empty array - no dummy qubit for empty set.
28 mutable power_products = [];
29 // Index to take next free qubit from aux_qubits array.
30 mutable next_available = 0;
31 // Consider every index in the input qubit register.
32 for qubit_index in IndexRange(qubits) {
33 // First, add the set that consists of only one qubit at index qubit_index.
34 power_products += qubits[qubit_index..qubit_index];
35 // Then, construct and add sets that include this new qubit as the last one.
36 for existing_set_index in 0..Length(power_products)-2 {
37 // Take the next qubit for the new set.
38 let next_power_product = aux_qubits[next_available];
39 next_available += 1;
40 // Create appropriate set and add it to the result.
41 AND(power_products[existing_set_index], qubits[qubit_index], next_power_product);
42 power_products += [next_power_product];
43 }
44 }
45 Fact(next_available == Length(aux_qubits), "ConstructPowerProducts: All auxiliary qubits should be used.");
46 return power_products;
47}
48
49/// # Summary
50/// Uncomputes construction of power products done by `ConstructPowerProducts`.
51/// Pass array returned by `ConstructPowerProducts` to this function
52/// to reset auxiliary qubits used to hold power products back to |0⟩ state.
53///
54/// # Description
55/// `products` array has no qubit that corresponds to an empty product (≡1).
56/// All entries at indexes `2^i - 1` contain original qubits.
57/// Qubits from `2^i - 1` to `2^(i+1) - 2` represent power products that
58/// end in original qubit at `2^i - 1`.
59/// To undo power products this function goes over original qubits backwards.
60/// Then measures out qubits from `2^i - 1` to `2^(i+1) - 2` in X basis,
61/// targeting corresponding qubits from 0 to `2^i - 2` in CZ gates if necessary.
62operation DestructPowerProducts(products : Qubit[]) : Unit {
63 let length = Length(products);
64 if length <= 1 {
65 // Nothing to undo - this was one of the source qubits.
66 return ();
67 }
68 // Adjust for empty set.
69 let extended_len = length + 1;
70 Fact((extended_len &&& length) == 0, "DestructPowerProducts: Length + 1 of a qubit register should be a power of 2");
71
72 // At index h-1 a source qubit is located (shifted by 1 to account for the lack of empty set).
73 // To the right are all power products ending in it.
74 // We are going backwards over all original qubits.
75 mutable h = extended_len / 2;
76 // If h is 1 we have nothing else to undo.
77 while h > 1 {
78 // Go over all sets that end in original qubit currently at index h-1.
79 // NOTE: The order of targets here doesn't matter.
80 for k in 0..h-2 {
81 // Measure and reset the qubit that represents
82 // the set (h-1) | k, which is at index h-1+k+1 = h+k.
83 if MResetX(products[h + k]) == One {
84 // If we measure 1, qubit representing set k needs to be included in targets.
85 CZ(products[h - 1], products[k]);
86 }
87 }
88 // Done with qubit at index h-1. Go to next original qubit.
89 h = h / 2;
90 }
91}
92
93function GetAuxCountForPP(nQubits : Int) : Int {
94 Fact(nQubits >= 0, "Number of qubits for power product construction must be non-negative.");
95 // Number of power products is 2^n - 1 (this excludes the empty product).
96 // Number of original qubits is n.
97 // Aux qubits needed is (2^n - 1) - n = 2^n - n - 1.
98 (1 <<< nQubits) - nQubits - 1
99}
100
101// =============================
102// Tests
103
104internal operation ConstructDestructPowerProducts(qs : Qubit[]) : Unit {
105 // For monomials with more than one variable we need auxiliary qubits.
106 use aux_qubits = Qubit[GetAuxCountForPP(Length(qs))];
107
108 // Construct/destruct should leave qs unchanged.
109 let products = ConstructPowerProducts(qs, aux_qubits);
110 DestructPowerProducts(products);
111}
112
113@Test()
114operation TestCreateDestructPowerProducts() : Unit {
115 // Check that construction and destruction of power products does not affect the register.
116 for i in 0..5 {
117 let success = CheckOperationsAreEqual(
118 i,
119 qs => ConstructDestructPowerProducts(qs),
120 qs => {}
121 );
122 Fact(success, $"Construction/Destruction of power products must be identity for {i} qubits.");
123 }
124}
125
126internal operation CheckPowerProducts(nQubits : Int, address_value : Int) : Unit {
127 // Prepare qubit register.
128 Fact(nQubits >= 0, "Number of qubits must be non-negative.");
129 use qs = Qubit[nQubits];
130 let address_space = 1 <<< nQubits;
131
132 // Prepare random basis state in qs.
133 Fact(address_value >= 0 and address_value < address_space, "Value must fit in the number of qubits.");
134 let state = Std.Convert.IntAsBoolArray(address_value, nQubits);
135 ApplyPauliFromBitString(PauliX, true, state, qs);
136
137 // Construct power products.
138 use aux_qubits = Qubit[GetAuxCountForPP(nQubits)];
139 let products = ConstructPowerProducts(qs, aux_qubits);
140 Fact(Length(products) == address_space - 1, $"Power product length should be {address_space - 1}.");
141
142 // Verify that each product qubit is correct.
143 for index in 0..address_space-2 {
144 // Shift by 1 since empty product is not included.
145 let monomial_index = index + 1;
146 mutable expected_value = true;
147 for bit_position in 0..nQubits-1 {
148 if ((monomial_index &&& (1 <<< bit_position)) != 0) {
149 // This qubit is included in the product.
150 set expected_value = expected_value and state[bit_position];
151 }
152 }
153 within {
154 if (expected_value) {
155 // Invert if expected value is 1 - we'll check for |0⟩ state.
156 X(products[index]);
157 }
158 } apply {
159 Fact(CheckZero(products[index]), $"Power product at index {index} should match expected value {expected_value}.");
160 }
161 }
162
163 // Destruct power products to reset aux qubits.
164 DestructPowerProducts(products);
165
166 // Reset original qubits.
167 ApplyPauliFromBitString(PauliX, true, state, qs);
168
169 // All qubits should be back to |0⟩ state at this point.
170}
171
172@Test()
173operation TestPowerProductsExhaustive() : Unit {
174 // Test power products construction for various numbers of qubits and basis states.
175 for nQubits in 0..5 {
176 let address_space = 1 <<< nQubits;
177 for value in 0..address_space-1 {
178 CheckPowerProducts(nQubits, value);
179 }
180 }
181}
182