GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
dbwy/random_seed

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/samples/algorithms

samples/algorithms/BernsteinVazirani.qs

167lines Β· modecode

RawDownload
Latest commit unavailable.
1/// # Sample
2/// Bernstein-Vazirani Algorithm
3///
4/// # Description
5/// The Bernstein-Vazirani algorithm determines the value of a bit string
6/// encoded in a function.
7///
8/// This Q# program implements the Bernstein-Vazirani algorithm.
9import Std.Arrays.*;
10import Std.Convert.*;
11import Std.Diagnostics.*;
12import Std.Math.*;
13import Std.Measurement.*;
14
15operation Main() : Int[] {
16 // Consider a function 𝑓(π‘₯βƒ—) on bitstrings π‘₯βƒ— = (π‘₯β‚€, …, π‘₯ₙ₋₁) of the form
17 // 𝑓(π‘₯βƒ—) ≔ Ξ£α΅’ π‘₯α΅’ π‘Ÿα΅’
18 // where π‘Ÿβƒ— = (π‘Ÿβ‚€, …, π‘Ÿβ‚™β‚‹β‚) is an unknown bitstring that determines the
19 // parity of 𝑓.
20
21 // The Bernstein–Vazirani algorithm allows determining π‘Ÿ given a
22 // quantum operation that implements
23 // |π‘₯βŒͺ|𝑦βŒͺ ↦ |π‘₯βŒͺ|𝑦 βŠ• 𝑓(π‘₯)βŒͺ.
24
25 // The entry point function of this program, `Main`, shows how to use
26 // the `BernsteinVazirani` operation to determine the value of various
27 // integers whose bits describe π‘Ÿ.
28 let nQubits = 10;
29
30 // Use the Bernstein–Vazirani algorithm to determine the bit strings
31 // that various integers represent.
32 let integers = [127, 238, 512];
33 mutable decodedIntegers = [];
34 for integer in integers {
35 // Create an operation that encodes a bit string represented by an
36 // integer as a parity operation.
37 let parityOperation = EncodeIntegerAsParityOperation(integer);
38
39 // Use the parity operation as input to the Bernstein-Vazirani
40 // algorithm to determine the bit string.
41 let decodedBitString = BernsteinVazirani(parityOperation, nQubits);
42 let decodedInteger = ResultArrayAsInt(decodedBitString);
43 decodedIntegers += [decodedInteger];
44 }
45
46 return decodedIntegers;
47}
48
49/// # Summary
50/// Validates the implementation of the Bernstein-Vazirani algorithm by
51/// comparing the decoded integers to the expected values.
52/// This also demonstrates how to use the `@Test` attribute to define a test operation.
53@Test()
54operation ValidateBernsteinVazirani() : Unit {
55 // To see how tests verify the behavior, try changing either the algorithm or the expected values
56 // in the assertion below and observe the test failure.
57 let integers = [127, 238, 512];
58 let results = Main();
59 Fact(results == integers, $"Decoded integers {results} do not match expected values {integers}");
60}
61
62/// # Summary
63/// This operation implements the Bernstein-Vazirani quantum algorithm.
64/// This algorithm computes for a given Boolean function that is promised to
65/// be a parity 𝑓(π‘₯β‚€, …, π‘₯ₙ₋₁) = Ξ£α΅’ π‘Ÿα΅’ π‘₯α΅’ a result in the form of a bit
66/// vector (π‘Ÿβ‚€, …, π‘Ÿβ‚™β‚‹β‚) corresponding to the parity function.
67/// Note that it is promised that the function is actually a parity
68/// function.
69///
70/// # Input
71/// ## Uf
72/// A quantum operation that implements |π‘₯βŒͺ|𝑦βŒͺ ↦ |π‘₯βŒͺ|𝑦 βŠ• 𝑓(π‘₯)βŒͺ,
73/// where 𝑓 is a Boolean function that implements a parity Ξ£α΅’ π‘Ÿα΅’ π‘₯α΅’.
74/// ## n
75/// The number of bits in the input register |π‘₯βŒͺ.
76///
77/// # Output
78/// An array of type `Result[]` that contains the parity π‘Ÿβƒ— = (π‘Ÿβ‚€, …, π‘Ÿβ‚™β‚‹β‚).
79///
80/// # See Also
81/// - For details see Section 1.4.3 of Nielsen & Chuang.
82///
83/// # References
84/// - [ *Ethan Bernstein and Umesh Vazirani*,
85/// SIAM J. Comput., 26(5), 1411–1473, 1997 ]
86/// (https://doi.org/10.1137/S0097539796300921)
87operation BernsteinVazirani(Uf : ((Qubit[], Qubit) => Unit), n : Int) : Result[] {
88 // We allocate n + 1 clean qubits. Note that the function Uf is defined
89 // on inputs of the form (x, y), where x has n bits and y has 1 bit.
90 use queryRegister = Qubit[n];
91 use target = Qubit();
92
93 // The last qubit needs to be flipped so that the function will actually
94 // be computed into the phase when Uf is applied.
95 X(target);
96
97 within {
98 // Now, a Hadamard transform is applied to each of the qubits. As
99 // the last step before the measurement, a Hadamard transform is
100 // applied to all qubits except last one. We could apply the
101 // transform to the last qubit also, but this would not affect the
102 // final outcome.
103 // We use a within-apply block to ensure that the Hadamard transform
104 // is correctly inverted.
105 ApplyToEachA(H, queryRegister);
106 } apply {
107 H(target);
108 // We now apply Uf to the n+1 qubits, computing
109 // |x, yβŒͺ ↦ |x, y βŠ• f(x)βŒͺ.
110 Uf(queryRegister, target);
111 }
112
113 // Measure all qubits and reset them to the |0βŒͺ state so that they can
114 // be safely deallocated at the end of the block.
115 let resultArray = MResetEachZ(queryRegister);
116
117 // Finally, the last qubit, which held the y-register, is reset.
118 Reset(target);
119
120 // The result is already contained in resultArray so no further
121 // post-processing is necessary.
122 return resultArray;
123}
124
125/// # Summary
126/// Given an integer that can be represented as a bit string
127/// π‘Ÿβƒ— = (rβ‚€, …, rₙ₋₁), this operation applies a unitary π‘ˆ that acts on 𝑛 + 1
128/// qubits as:
129/// π‘ˆ |π‘₯βŒͺ|𝑦βŒͺ = |π‘₯βŒͺ|𝑦 βŠ• 𝑓(π‘₯)βŒͺ
130/// where 𝑓(π‘₯) = Ξ£α΅’ π‘₯α΅’ π‘Ÿα΅’ mod 2.
131///
132/// # Input
133/// ## bitStringAsInt
134/// An integer that can be represented as a bit string π‘Ÿβƒ— used to define the
135/// function 𝑓.
136/// ## xRegister
137/// Represents the |π‘₯βŒͺ register that π‘ˆ acts on.
138/// ## yQubit
139/// Represents the |𝑦βŒͺ qubit that π‘ˆ acts on.
140operation ApplyParityOperation(
141 bitStringAsInt : Int,
142 xRegister : Qubit[],
143 yQubit : Qubit
144) : Unit {
145 // `xRegister` muts have enough qubits to represent the integer.
146 let requiredBits = BitSizeI(bitStringAsInt);
147 let availableQubits = Length(xRegister);
148 Fact(
149 availableQubits >= requiredBits,
150 $"Integer value {bitStringAsInt} requires {requiredBits} bits to be represented but the quantum register only has {availableQubits} qubits"
151 );
152
153 // Apply the quantum operations that encode the bit string.
154 for index in IndexRange(xRegister) {
155 if ((bitStringAsInt &&& 2^index) != 0) {
156 CNOT(xRegister[index], yQubit);
157 }
158 }
159}
160
161/// # Summary
162/// Returns black-box operations (Qubit[], Qubit) => () of the form
163/// U_f |π‘₯βŒͺ|𝑦βŒͺ = |π‘₯βŒͺ|𝑦 βŠ• 𝑓(π‘₯)βŒͺ.
164/// We define 𝑓 by providing the bit string π‘Ÿβƒ— as an integer.
165function EncodeIntegerAsParityOperation(bitStringAsInt : Int) : (Qubit[], Qubit) => Unit {
166 return ApplyParityOperation(bitStringAsInt, _, _);
167}