microsoft/qdk
Publicmirrored from https://github.com/microsoft/qdkAvailable
samples/algorithms/BernsteinVaziraniNISQ.qs
149lines · modecode
| 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. |
| 9 | import Std.Arrays.*; |
| 10 | import Std.Convert.*; |
| 11 | import Std.Diagnostics.*; |
| 12 | import Std.Math.*; |
| 13 | import Std.Measurement.*; |
| 14 | |
| 15 | operation Main() : Result[] { |
| 16 | // Consider a function 𝑓(𝑥⃗) on bitstrings 𝑥⃗ = (𝑥₀, …, 𝑥ₙ₋₁) of the form |
| 17 | // 𝑓(𝑥⃗) ≔ Σᵢ 𝑥ᵢ 𝑟ᵢ |
| 18 | // where 𝑟⃗ = (𝑟₀, …, 𝑟ₙ₋₁) is an unknown bit string that determines the |
| 19 | // parity of 𝑓. |
| 20 | |
| 21 | // The Bernstein–Vazirani algorithm allows determining 𝑟 given a |
| 22 | // quantum operation that implements |
| 23 | // |𝑥〉|𝑦〉 ↦ |𝑥〉|𝑦 ⊕ 𝑓(𝑥)〉. |
| 24 | |
| 25 | // This entry point function of this program, `Main`, shows how to use |
| 26 | // the `BernsteinVazirani` operation to determine the value of bitstring |
| 27 | // 𝑟. |
| 28 | let secretBitString = SecretBitStringAsBoolArray(); |
| 29 | let parityOperation = EncodeBitStringAsParityOperation(secretBitString); |
| 30 | let decodedBitString = BernsteinVazirani( |
| 31 | parityOperation, |
| 32 | Length(secretBitString) |
| 33 | ); |
| 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) : Result[] { |
| 64 | // We allocate n + 1 clean qubits. Note that the function parameter Uf is defined |
| 65 | // on inputs of the form (x, y), where x has n bits and y has 1 bit. |
| 66 | use queryRegister = Qubit[n]; |
| 67 | use target = Qubit(); |
| 68 | |
| 69 | // The last qubit needs to be flipped so that a relative phase is |
| 70 | // introduced when we apply a Hadamard gate later on and we can use |
| 71 | // phase kickback when Uf is applied. |
| 72 | X(target); |
| 73 | |
| 74 | within { |
| 75 | // Now, a Hadamard transform is applied to each of the qubits. As |
| 76 | // the last step before the measurement, a Hadamard transform is |
| 77 | // applied to all qubits except the last one. We could also |
| 78 | // transform the last qubit, but this would not affect the |
| 79 | // final outcome. |
| 80 | // We use a within-apply block to ensure that the Hadamard transform |
| 81 | // is correctly inverted. |
| 82 | ApplyToEachA(H, queryRegister); |
| 83 | } apply { |
| 84 | H(target); |
| 85 | // We now apply Uf to the n+1 qubits, computing |
| 86 | // |x, y〉 ↦ |x, y ⊕ f(x)〉. |
| 87 | Uf(queryRegister, target); |
| 88 | } |
| 89 | |
| 90 | // Measure all qubits and reset them to the |0〉 state so that they can |
| 91 | // be safely deallocated at the end of the block. |
| 92 | let resultArray = MResetEachZ(queryRegister); |
| 93 | |
| 94 | // Finally, the last qubit, which held the y-register, is reset. |
| 95 | Reset(target); |
| 96 | |
| 97 | // The result is already contained in resultArray so no further |
| 98 | // post-processing is necessary. |
| 99 | return resultArray; |
| 100 | } |
| 101 | |
| 102 | /// # Summary |
| 103 | /// Given bit string 𝑟⃗ = (r₀, …, rₙ₋₁), represented as an array of Booleans, |
| 104 | /// this operation applies a unitary 𝑈 that acts on 𝑛 + 1 qubits as: |
| 105 | /// 𝑈 |𝑥〉|𝑦〉 = |𝑥〉|𝑦 ⊕ 𝑓(𝑥)〉 |
| 106 | /// where 𝑓(𝑥) = Σᵢ 𝑥ᵢ 𝑟ᵢ mod 2. |
| 107 | /// |
| 108 | /// # Input |
| 109 | /// ## bitStringAsBoolArray |
| 110 | /// A bit string 𝑟⃗, represented as an array of Booleans, used to define the |
| 111 | /// function 𝑓. |
| 112 | /// ## xRegister |
| 113 | /// Represents the |𝑥〉 register that 𝑈 acts on. |
| 114 | /// ## yQubit |
| 115 | /// Represents the |𝑦〉 qubit that 𝑈 acts on. |
| 116 | operation ApplyParityOperation( |
| 117 | bitStringAsBoolArray : Bool[], |
| 118 | xRegister : Qubit[], |
| 119 | yQubit : Qubit |
| 120 | ) : Unit { |
| 121 | // `xRegister` muts have enough qubits to represent the integer. |
| 122 | let requiredBits = Length(bitStringAsBoolArray); |
| 123 | let availableQubits = Length(xRegister); |
| 124 | Fact( |
| 125 | availableQubits >= requiredBits, |
| 126 | $"The bitstring has {requiredBits} bits but the quantum register " + $"only has {availableQubits} qubits" |
| 127 | ); |
| 128 | |
| 129 | // Apply the quantum operations that encode the bit string. |
| 130 | for (index, bit) in Enumerated(bitStringAsBoolArray) { |
| 131 | if bit { |
| 132 | CNOT(xRegister[index], yQubit); |
| 133 | } |
| 134 | } |
| 135 | } |
| 136 | |
| 137 | /// # Summary |
| 138 | /// This is a higher-order operation which returns an operation (Qubit[], Qubit) => () of the form |
| 139 | /// U_f |𝑥〉|𝑦〉 = |𝑥〉|𝑦 ⊕ 𝑓(𝑥)〉. |
| 140 | /// We define 𝑓 by providing the bit string 𝑟⃗ as an integer. |
| 141 | function EncodeBitStringAsParityOperation(bitStringAsBoolArray : Bool[]) : (Qubit[], Qubit) => Unit { |
| 142 | return ApplyParityOperation(bitStringAsBoolArray, _, _); |
| 143 | } |
| 144 | |
| 145 | /// # Summary |
| 146 | /// Returns a particular bit string as an array of Booleans. |
| 147 | function SecretBitStringAsBoolArray() : Bool[] { |
| 148 | return [true, false, true, false, true]; |
| 149 | } |
| 150 | |