GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
v1.0.10-rc

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/samples/algorithms

samples/algorithms/HiddenShift.qs

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