GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
9831093db0098b3a3e55cbadf3929222d7dd4805

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/samples/algorithms

samples/algorithms/HiddenShift.qs

172lines Β· modecode

RawDownload
Latest commit unavailable.
1/// # Sample
2/// Hidden Shift
3///
4/// # Description
5/// There is a family of problems known as hidden shift problems, in which it
6/// is given that two Boolean functions 𝑓 and 𝑔 satisfy the relation
7/// 𝑔(π‘₯) = 𝑓(π‘₯ βŠ• 𝑠) for all π‘₯
8/// where 𝑠 is a hidden bit string that we would like to find.
9///
10/// This Q# program implements an algorithm to solve the hidden shift problem.
11import Std.Arrays.*;
12import Std.Convert.*;
13import Std.Diagnostics.*;
14import Std.Measurement.*;
15
16operation Main() : Int[] {
17 let nQubits = 10;
18
19 // Consider the case of finding a hidden shift 𝑠 between two Boolean
20 // functions 𝑓(π‘₯) and 𝑔(π‘₯) = 𝑓(π‘₯ βŠ• 𝑠).
21 // This problem can be solved on a quantum computer with one call to
22 // each of 𝑓 and 𝑔 in the special case that both functions are bent;
23 // that is, that they are as far from linear as possible.
24
25 // Here, we find the hidden shift for various pairs of bent functions.
26 let shifts = [170, 512, 999];
27 mutable hiddenShifts = [];
28 for shift in shifts {
29 let hiddenShiftBitString = FindHiddenShift(
30 BentFunction,
31 register => ShiftedBentFunction(shift, register),
32 nQubits
33 );
34 let hiddenShift = ResultArrayAsInt(hiddenShiftBitString);
35 Message($"Found {shift} successfully!");
36 hiddenShifts += [hiddenShift];
37 }
38
39 // Note: returned array should match shifts array
40 return hiddenShifts;
41}
42
43/// # Summary
44/// Implements a correlation-based algorithm to solve the hidden shift
45/// problem for bent functions.
46///
47/// # Description
48/// Implements a solution for the hidden shift problem, which is to identify
49/// an unknown shift 𝑠 of the arguments of two Boolean functions 𝑓 and 𝑔
50/// that are promised to satisfy the relation 𝑔(π‘₯) = 𝑓(π‘₯ βŠ• 𝑠) for all π‘₯.
51///
52/// 𝑓 and 𝑔 are assumed to be bent functions. A Boolean function is bent if
53/// it is as far from linear as possible. In particular, bent functions have
54/// flat Fourier (Walsh–Hadamard) spectra.
55///
56/// In this case, the Roetteler algorithm (see References, below) uses
57/// black-box oracles for 𝑓^* and 𝑔, where 𝑓^* is the dual bent function to
58/// 𝑓, and computes the hidden shift 𝑠 between 𝑓 and 𝑔.
59///
60/// # Input
61/// ## Ufstar
62/// A quantum operation that implements
63/// $U_f^*: |π‘₯βŒͺ ↦ (-1)^{f^*(x)} |π‘₯βŒͺ$,
64/// where $f^*$ is a Boolean function, π‘₯ is an $n$ bit register
65/// ## Ug
66/// A quantum operation that implements
67/// $U_g:|π‘₯βŒͺ ↦ (-1)^{g(x)} |π‘₯βŒͺ$,
68/// where 𝑔 is a Boolean function that is shifted by unknown
69/// 𝑠 from 𝑓, and π‘₯ is an $n$ bit register.
70/// ## n
71/// The number of bits of the input register |π‘₯βŒͺ.
72///
73/// # Output
74/// An array of type `Result[]` which encodes the bit representation
75/// of the hidden shift.
76///
77/// # References
78/// - [*Martin Roetteler*,
79/// Proc. SODA 2010, ACM, pp. 448-457, 2010]
80/// (https://doi.org/10.1137/1.9781611973075.37)
81operation FindHiddenShift(
82 Ufstar : (Qubit[] => Unit),
83 Ug : (Qubit[] => Unit),
84 n : Int
85) : Result[] {
86 // We allocate n clean qubits. Note that the function Ufstar and Ug are
87 // unitary operations on n qubits defined via phase encoding.
88 use qubits = Qubit[n];
89
90 // First, a Hadamard transform is applied to each of the qubits.
91 ApplyToEach(H, qubits);
92
93 // We now apply the shifted function Ug to the n qubits, computing
94 // |xβŒͺ -> (-1)^{g(x)} |xβŒͺ.
95 Ug(qubits);
96
97 within {
98 // A Hadamard transform is applied to each of the n qubits.
99 ApplyToEachA(H, qubits);
100 } apply {
101 // we now apply the dual function of the unshifted function, i.e.,
102 // Ufstar, to the n qubits, computing |xβŒͺ -> (-1)^{fstar(x)} |xβŒͺ.
103 Ufstar(qubits);
104 }
105
106 // Measure the n qubits and reset them to zero so that they can be
107 // safely deallocated at the end of the block.
108 return MResetEachZ(qubits);
109}
110
111/// # Summary
112/// Implements an oracle for a bent function constructed from the inner
113/// product of Boolean functions.
114///
115/// # Description
116/// This operation defines the Boolean function IP(x_0, ..., x_{n-1}) which
117/// is computed into the phase, i.e., a diagonal operator that maps
118/// |xβŒͺ -> (-1)^{IP(x)} |xβŒͺ, where x stands for x=(x_0, ..., x_{n-1}) and all
119/// the x_i are binary. The IP function is defined as
120/// IP(y, z) = y_0 z_0 + y_1 z_1 + ... y_{u-1} z_{u-1} where
121/// y = (y_0, ..., y_{u-1}) and z = (z_0, ..., z_{u-1}) are two bit vectors
122/// of length u. Notice that the function IP is a Boolean function on n = 2u
123/// bits. IP is a special case of bent function. These are functions for
124/// which the Walsh-Hadamard transform is perfectly flat (in absolute
125/// value).
126/// Because of this flatness, the Walsh-Hadamard spectrum of any bent
127/// function defines a +1/-1 function, i.e., gives rise to another Boolean
128/// function, called the dual bent function. Moreover, for the case of the
129/// IP function it can be shown that IP is equal to its own dual bent
130/// function.
131///
132/// # Remarks
133/// Notice that a diagonal operator implementing IP between 2 variables y_0
134/// and z_0 is nothing but the AND function between those variables, i.e.,
135/// in phase encoding it is computed by a Controlled-Z gate.
136/// Extending this to an XOR of the AND of more variables, as required in
137/// the definition of the IP function can then be accomplished by applying
138/// several Controlled-Z gates between the respective inputs.
139operation BentFunction(register : Qubit[]) : Unit {
140 Fact(Length(register) % 2 == 0, "Length of register must be even.");
141 let u = Length(register) / 2;
142 let xs = register[0..u - 1];
143 let ys = register[u...];
144 for index in 0..u - 1 {
145 CZ(xs[index], ys[index]);
146 }
147}
148
149/// # Summary
150/// Implements a shifted bend function 𝑔(π‘₯) = 𝑓(π‘₯ βŠ• 𝑠).
151///
152/// # Description
153/// For the hidden shift problem we need another function g which is related
154/// to IP via g(x) = IP(x + s), i.e., we have to shift the argument of the
155/// IP function by a given shift. Notice that the '+' operation here is the
156/// Boolean addition, i.e., a bit-wise operation. Notice further, that in
157/// general a diagonal operation |xβŒͺ -> (-1)^{f(x)} can be turned into a
158/// shifted version by applying a bit flip to the |xβŒͺ register first, then
159/// applying the diagonal operation, and then undoing the bit flips to the
160/// |xβŒͺ register. We use this principle to define shifted versions of the IP
161/// operation.
162operation ShiftedBentFunction(shift : Int, register : Qubit[]) : Unit {
163 Fact(Length(register) % 2 == 0, "Length of register must be even.");
164 let u = Length(register) / 2;
165 within {
166 // Flips the bits in shift.
167 ApplyXorInPlace(shift, register);
168 } apply {
169 // Compute the IP function into the phase.
170 BentFunction(register);
171 }
172}
173