GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
alex/pythontelem

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/samples/algorithms

samples/algorithms/BernsteinVazirani.qs

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