GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
v1.25.1

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/samples/algorithms

samples/algorithms/BernsteinVazirani.qs

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