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/BernsteinVaziraniNISQ.qs

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