GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored from https://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
jan

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/samples/algorithms

samples/algorithms/HiddenShift.qs

172lines · modeblame

RawDownload
Latest commit unavailable.
bf366214César Zaragoza Cortés3 years ago1/// # Sample
efeac5cbScott Carda1 years ago2/// Hidden Shift
bf366214César Zaragoza Cortés3 years ago3///
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.
91f754e1Scott Carda1 years ago11import Std.Arrays.*;
12import Std.Convert.*;
13import Std.Diagnostics.*;
14import Std.Measurement.*;
bf366214César Zaragoza Cortés3 years ago15
91f754e1Scott Carda1 years ago16operation Main() : Int[] {
17let nQubits = 10;
bf366214César Zaragoza Cortés3 years ago18
91f754e1Scott Carda1 years ago19// 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.
bf366214César Zaragoza Cortés3 years ago24
91f754e1Scott Carda1 years ago25// Here, we find the hidden shift for various pairs of bent functions.
26let shifts = [170, 512, 999];
27mutable hiddenShifts = [];
28for shift in shifts {
29let hiddenShiftBitString = FindHiddenShift(
30BentFunction,
31register => ShiftedBentFunction(shift, register),
32nQubits
33);
34let hiddenShift = ResultArrayAsInt(hiddenShiftBitString);
35Message($"Found {shift} successfully!");
e0df7cc6Filip W1 years ago36hiddenShifts += [hiddenShift];
bf366214César Zaragoza Cortés3 years ago37}
38
91f754e1Scott Carda1 years ago39// Note: returned array should match shifts array
40return hiddenShifts;
41}
bf366214César Zaragoza Cortés3 years ago42
91f754e1Scott Carda1 years ago43/// # 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(
82Ufstar : (Qubit[] => Unit),
83Ug : (Qubit[] => Unit),
84n : 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.
88use qubits = Qubit[n];
bf366214César Zaragoza Cortés3 years ago89
91f754e1Scott Carda1 years ago90// First, a Hadamard transform is applied to each of the qubits.
91ApplyToEach(H, qubits);
bf366214César Zaragoza Cortés3 years ago92
91f754e1Scott Carda1 years ago93// We now apply the shifted function Ug to the n qubits, computing
94// |x〉 -> (-1)^{g(x)} |x〉.
95Ug(qubits);
bf366214César Zaragoza Cortés3 years ago96
91f754e1Scott Carda1 years ago97within {
98// A Hadamard transform is applied to each of the n qubits.
99ApplyToEachA(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〉.
103Ufstar(qubits);
bf366214César Zaragoza Cortés3 years ago104}
105
91f754e1Scott Carda1 years ago106// Measure the n qubits and reset them to zero so that they can be
107// safely deallocated at the end of the block.
108return 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 {
140Fact(Length(register) % 2 == 0, "Length of register must be even.");
141let u = Length(register) / 2;
142let xs = register[0..u - 1];
143let ys = register[u...];
144for index in 0..u - 1 {
145CZ(xs[index], ys[index]);
bf366214César Zaragoza Cortés3 years ago146}
91f754e1Scott Carda1 years ago147}
bf366214César Zaragoza Cortés3 years ago148
91f754e1Scott Carda1 years ago149/// # 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 {
163Fact(Length(register) % 2 == 0, "Length of register must be even.");
164let u = Length(register) / 2;
165within {
166// Flips the bits in shift.
167ApplyXorInPlace(shift, register);
168} apply {
169// Compute the IP function into the phase.
170BentFunction(register);
bf366214César Zaragoza Cortés3 years ago171}
172}