GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
billt/revert-mimalloc

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 open Microsoft.Quantum.Arrays;
11 open Microsoft.Quantum.Convert;
12 open Microsoft.Quantum.Diagnostics;
13 open Microsoft.Quantum.Math;
14 open Microsoft.Quantum.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, Length(secretBitString));
34
35 return decodedBitString;
36 }
37
38 /// # Summary
39 /// This operation implements the Bernstein-Vazirani quantum algorithm.
40 /// This algorithm computes for a given Boolean function that is promised to
41 /// be a parity 𝑓(𝑥₀, …, 𝑥ₙ₋₁) = Σᵢ 𝑟ᵢ 𝑥ᵢ a result in the form of a bit
42 /// vector (𝑟₀, …, 𝑟ₙ₋₁) corresponding to the parity function.
43 /// Note that it is promised that the function is actually a parity
44 /// function.
45 ///
46 /// # Input
47 /// ## Uf
48 /// A quantum operation that implements |𝑥〉|𝑦〉 ↦ |𝑥〉|𝑦 ⊕ 𝑓(𝑥)〉,
49 /// where 𝑓 is a Boolean function that implements a parity Σᵢ 𝑟ᵢ 𝑥ᵢ.
50 /// ## n
51 /// The number of bits in the input register |𝑥〉.
52 ///
53 /// # Output
54 /// An array of type `Result[]` that contains the parity 𝑟⃗ = (𝑟₀, …, 𝑟ₙ₋₁).
55 ///
56 /// # See Also
57 /// - For details see Section 1.4.3 of Nielsen & Chuang.
58 ///
59 /// # References
60 /// - [ *Ethan Bernstein and Umesh Vazirani*,
61 /// SIAM J. Comput., 26(5), 1411–1473, 1997 ]
62 /// (https://doi.org/10.1137/S0097539796300921)
63 operation BernsteinVazirani(Uf : ((Qubit[], Qubit) => Unit), n : Int)
64 : Result[] {
65 // We allocate n + 1 clean qubits. Note that the function parameter Uf is defined
66 // on inputs of the form (x, y), where x has n bits and y has 1 bit.
67 use queryRegister = Qubit[n];
68 use target = Qubit();
69
70 // The last qubit needs to be flipped so that a relative phase is
71 // introduced when we apply a Hadamard gate later on and we can use
72 // phase kickback when Uf is applied.
73 X(target);
74
75 within {
76 // Now, a Hadamard transform is applied to each of the qubits. As
77 // the last step before the measurement, a Hadamard transform is
78 // applied to all qubits except the last one. We could also
79 // transform the last qubit, but this would not affect the
80 // final outcome.
81 // We use a within-apply block to ensure that the Hadamard transform
82 // is correctly inverted.
83 ApplyToEachA(H, queryRegister);
84 } apply {
85 H(target);
86 // We now apply Uf to the n+1 qubits, computing
87 // |x, y〉 ↦ |x, y ⊕ f(x)〉.
88 Uf(queryRegister, target);
89 }
90
91 // Measure all qubits and reset them to the |0〉 state so that they can
92 // be safely deallocated at the end of the block.
93 let resultArray = ForEach(MResetZ, queryRegister);
94
95 // Finally, the last qubit, which held the y-register, is reset.
96 Reset(target);
97
98 // The result is already contained in resultArray so no further
99 // post-processing is necessary.
100 return resultArray;
101 }
102
103 /// # Summary
104 /// Given bit string 𝑟⃗ = (r₀, …, rₙ₋₁), represented as an array of Booleans,
105 /// this operation applies a unitary 𝑈 that acts on 𝑛 + 1 qubits as:
106 /// 𝑈 |𝑥〉|𝑦〉 = |𝑥〉|𝑦 ⊕ 𝑓(𝑥)〉
107 /// where 𝑓(𝑥) = Σᵢ 𝑥ᵢ 𝑟ᵢ mod 2.
108 ///
109 /// # Input
110 /// ## bitStringAsBoolArray
111 /// A bit string 𝑟⃗, represented as an array of Booleans, used to define the
112 /// function 𝑓.
113 /// ## xRegister
114 /// Represents the |𝑥〉 register that 𝑈 acts on.
115 /// ## yQubit
116 /// Represents the |𝑦〉 qubit that 𝑈 acts on.
117 operation ApplyParityOperation(
118 bitStringAsBoolArray : Bool[],
119 xRegister : Qubit[],
120 yQubit : Qubit)
121 : Unit {
122 // `xRegister` muts have enough qubits to represent the integer.
123 let requiredBits = Length(bitStringAsBoolArray);
124 let availableQubits = Length(xRegister);
125 Fact(
126 availableQubits >= requiredBits,
127 $"The bitstring has {requiredBits} bits but the quantum register " +
128 $"only has {availableQubits} qubits");
129
130 // Apply the quantum operations that encode the bit string.
131 for (index, bit) in Enumerated(bitStringAsBoolArray) {
132 if bit {
133 CNOT(xRegister[index], yQubit);
134 }
135 }
136 }
137
138 /// # Summary
139 /// This is a higher-order operation which returns an operation (Qubit[], Qubit) => () of the form
140 /// U_f |𝑥〉|𝑦〉 = |𝑥〉|𝑦 ⊕ 𝑓(𝑥)〉.
141 /// We define 𝑓 by providing the bit string 𝑟⃗ as an integer.
142 operation EncodeBitStringAsParityOperation(bitStringAsBoolArray : Bool[])
143 : (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}