GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
brlackey/ising-model-sample

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

198lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4// Simple implementations of lookup operations using multicontrolled X gates.
5// Data shorter or longer than addressable space is allowed:
6// * Longer data is ignored.
7// * Shorter data is treated as if it is padded with false values.
8// Little-endian format is used throughout.
9
10import Std.Arrays.IndexRange;
11import Std.Diagnostics.*;
12import Std.Math.*;
13
14// Lookup of a single bit using multicontrolled X gates.
15operation BitLookupViaMCX(data : Bool[], address : Qubit[], target : Qubit) : Unit is Adj + Ctl {
16 let address_size = Length(address);
17 let addressable_space = 2^address_size;
18 let data_length = Length(data);
19 for basis_vector in 0..MinI(data_length, addressable_space)-1 {
20 if data[basis_vector] {
21 within {
22 // Invert address qubits for 0-es in basis_vector.
23 ApplyXorInPlace(addressable_space-1-basis_vector, address)
24 } apply {
25 Controlled X(address, target);
26 }
27 }
28 }
29}
30
31// Phase lookup of a single bit using multicontrolled X gates.
32operation PhaseLookupViaMCX(data : Bool[], address : Qubit[]) : Unit is Adj + Ctl {
33 use aux = Qubit();
34 within {
35 X(aux);
36 H(aux);
37 } apply {
38 BitLookupViaMCX(data, address, aux);
39 }
40}
41
42// Lookup of mult-bit register using multicontrolled X gates.
43operation LookupViaMCX(data : Bool[][], address : Qubit[], target : Qubit[]) : Unit is Adj + Ctl {
44 let address_size = Length(address);
45 let addressable_space = 2^address_size;
46 let data_length = Length(data);
47 let target_size = Length(target);
48 for basis_vector in 0..MinI(data_length, addressable_space)-1 {
49 let data_vector = data[basis_vector];
50 Fact(Length(data_vector) == target_size, $"Data vector length {Length(data_vector)} must match target size {target_size}.");
51 within {
52 // Invert address qubits for 0-es in basis_vector.
53 ApplyXorInPlace(addressable_space-1-basis_vector, address)
54 } apply {
55 Controlled ApplyPauliFromBitString(address, (PauliX, true, data_vector, target));
56 }
57 }
58}
59
60// =============================
61// Tests
62
63@Test()
64operation CheckLookupViaMCX() : Unit {
65 let n = 3;
66 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]];
67
68 use addr = Qubit[n];
69 use target = Qubit[3];
70
71 // Check that data at all indices is looked up correctly.
72 for i in IndexRange(data) {
73 ApplyXorInPlace(i, addr);
74 LookupViaMCX(data, addr, target);
75
76 ApplyPauliFromBitString(PauliX, true, data[i], target);
77 let zero = CheckAllZero(target);
78 Fact(zero, $"Target should match {data[i]} at index {i}.");
79 ResetAll(addr);
80 }
81}
82
83@Test()
84operation CheckLookupViaMCXShorterData() : Unit {
85 let n = 3;
86 let width = 3;
87 let data = [[true, false, false], [false, true, false], [false, false, true]];
88
89 use addr = Qubit[n];
90 use target = Qubit[width];
91
92 // Check that shorter data at all indices is looked up correctly.
93 for i in 0..2^n-1 {
94 ApplyXorInPlace(i, addr);
95 LookupViaMCX(data, addr, target);
96
97 mutable expected_data = [false, false, false];
98 if i < Length(data) {
99 ApplyPauliFromBitString(PauliX, true, data[i], target);
100 set expected_data = data[i];
101 } else {
102 // For out-of-bounds indices, target should remain |0...0⟩.
103 }
104 let zero = CheckAllZero(target);
105 Fact(zero, $"Target should match {expected_data} at index {i}.");
106 ResetAll(addr);
107 }
108}
109
110@Test()
111operation CheckLookupViaMCXLongerData() : Unit {
112 let n = 2;
113 let width = 3;
114 let data = [[true, false, false], [false, true, false], [false, false, true], [false, false, false], [true, true, false], [false, true, true], [true, true, true]];
115
116 use addr = Qubit[n];
117 use target = Qubit[width];
118
119 // Check that longer data at all available indices is looked up correctly.
120 for i in 0..2^n-1 {
121 ApplyXorInPlace(i, addr);
122 LookupViaMCX(data, addr, target);
123
124 ApplyPauliFromBitString(PauliX, true, data[i], target);
125 let zero = CheckAllZero(target);
126 Fact(zero, $"Target should match {data[i]} at index {i}.");
127 ResetAll(addr);
128 }
129}
130
131@Test()
132operation CheckBitLookupViaMCX() : Unit {
133 let n = 4;
134 let data = [true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, true];
135
136 use addr = Qubit[n];
137 use target = Qubit();
138
139 // Check that data at all indices is looked up correctly.
140 for i in IndexRange(data) {
141 ApplyXorInPlace(i, addr);
142 BitLookupViaMCX(data, addr, target);
143
144 let value = Std.Convert.ResultAsBool(MResetZ(target));
145 ResetAll(addr);
146
147 Fact(value == data[i], $"Target qubit measurement mismatch at index {i}.");
148 }
149}
150
151@Test()
152operation TestPhaseLookupViaMCX() : Unit {
153 let n = 4;
154 let data = [true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, true];
155 let coeffs = [-0.25, 0.25, -0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, -0.25, -0.25];
156
157 use qs = Qubit[n];
158 ApplyToEach(H, qs);
159
160 // `Reversed` to match big-endian state preparation coefficients order.
161 PhaseLookupViaMCX(data, Std.Arrays.Reversed(qs));
162 Adjoint Std.StatePreparation.PreparePureStateD(coeffs, qs);
163
164 Fact(CheckAllZero(qs), "All qubits should be back to |0⟩ state.");
165}
166
167@Test()
168operation TestBitLookupViaMCXMatchesStd() : Unit {
169 let n = 4;
170 let data = [true, false, true, false, false, false, false, false, true, false, false, true, false, false, true, true];
171 let select_data = Std.Arrays.Mapped(x -> [x], data);
172
173 // Use adjoint Std.TableLookup.Select because this check takes adjoint of that.
174 let equal = CheckOperationsAreEqual(
175 n + 1,
176 qs => BitLookupViaMCX(data, qs[0..n-1], qs[n]),
177 qs => Adjoint Std.TableLookup.Select(select_data, qs[0..n-1], qs[n..n])
178 );
179 Fact(equal, "BitLookupViaMCX should match Std.TableLookup.Select.");
180}
181
182@Test()
183operation TestLookupViaMCXMatchesStd() : Unit {
184 let n = 3;
185 let width = 4;
186 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]];
187
188 use addr = Qubit[n];
189 use target = Qubit[width];
190
191 // Use adjoint Std.TableLookup.Select because this check takes adjoint of that.
192 let equal = CheckOperationsAreEqual(
193 n + width,
194 qs => LookupViaMCX(data, qs[0..n-1], qs[n...]),
195 qs => Adjoint Std.TableLookup.Select(data, qs[0..n-1], qs[n...])
196 );
197 Fact(equal, "LookupViaMCX should match Std.TableLookup.Select.");
198}
199