microsoft/qdk
Publicmirrored from https://github.com/microsoft/qdkAvailable
samples/estimation/df-chemistry/src/prepare.qs
223lines · modecode
| 1 | // Copyright (c) Microsoft Corporation. All rights reserved. |
| 2 | // Licensed under the MIT License. |
| 3 | namespace Microsoft.Quantum.Applications.Chemistry { |
| 4 | open Microsoft.Quantum.Arrays; |
| 5 | open Microsoft.Quantum.Convert; |
| 6 | open Microsoft.Quantum.Diagnostics; |
| 7 | open Microsoft.Quantum.Intrinsic; |
| 8 | open Microsoft.Quantum.Math; |
| 9 | open Microsoft.Quantum.Unstable.Arithmetic; |
| 10 | open Microsoft.Quantum.Unstable.TableLookup; |
| 11 | |
| 12 | // ------------------------------------- // |
| 13 | // State preparation (public operations) // |
| 14 | // ------------------------------------- // |
| 15 | |
| 16 | operation PrepareSingleQubit(p0 : Double, p1 : Double, target : Qubit) : Unit is Adj + Ctl { |
| 17 | let oneNorm = p0 + p1; |
| 18 | let alpha = ArcCos(Sqrt(p0 / oneNorm)); |
| 19 | |
| 20 | Ry(2.0 * alpha, target); |
| 21 | } |
| 22 | |
| 23 | operation PrepareUniformSuperposition(numStates : Int, qs : Qubit[]) : Unit is Adj + Ctl { |
| 24 | Fact(numStates >= 1, "numStates must be positive"); |
| 25 | Fact(numStates <= 2^Length(qs), $"numStates must be smaller or equal to {2^Length(qs)}"); |
| 26 | |
| 27 | let qsAdjusted = qs[...Ceiling(Lg(IntAsDouble(numStates))) - 1]; |
| 28 | |
| 29 | let (factor, pow) = DecomposePowerOf2(numStates); |
| 30 | |
| 31 | if factor == 1 { |
| 32 | ApplyToEachCA(H, qsAdjusted[0..pow - 1]); |
| 33 | } else { |
| 34 | use tgt = Qubit(); |
| 35 | |
| 36 | let sqrt = Sqrt(IntAsDouble(1 <<< Length(qsAdjusted)) / IntAsDouble(numStates)); |
| 37 | let angle = 2.0 * ArcSin(0.5 * sqrt); |
| 38 | |
| 39 | ApplyToEachCA(H, qsAdjusted); |
| 40 | |
| 41 | ApplyIfGreaterL(Ry(2.0 * angle, _), IntAsBigInt(numStates), qsAdjusted, tgt); |
| 42 | |
| 43 | within { |
| 44 | ApplyToEachA(H, qsAdjusted[pow...]); |
| 45 | } apply { |
| 46 | ReflectAboutInteger(0, qsAdjusted[pow...] + [tgt]); |
| 47 | Ry(-angle, tgt); |
| 48 | } |
| 49 | |
| 50 | X(tgt); |
| 51 | } |
| 52 | } |
| 53 | |
| 54 | newtype PrepareArbitrarySuperposition = ( |
| 55 | NIndexQubits: Int, |
| 56 | NGarbageQubits: Int, |
| 57 | Prepare: (Qubit[], Qubit[], Qubit[]) => Unit is Adj + Ctl, |
| 58 | PrepareWithSelect: ((Bool[][], Qubit[], Qubit[]) => Unit is Adj + Ctl, Qubit[], Qubit[], Qubit[]) => Unit is Adj + Ctl |
| 59 | ); |
| 60 | |
| 61 | function MakePrepareArbitrarySuperposition(targetError : Double, coefficients : Double[]) |
| 62 | : PrepareArbitrarySuperposition { |
| 63 | let nBitsPrecision = -Ceiling(Lg(0.5 * targetError)) + 1; |
| 64 | let positiveCoefficients = Mapped(AbsD, coefficients); |
| 65 | let (keepCoeff, altIndex) = DiscretizedProbabilityDistribution(nBitsPrecision, positiveCoefficients); |
| 66 | let nCoeffs = Length(positiveCoefficients); |
| 67 | let nBitsIndices = Ceiling(Lg(IntAsDouble(nCoeffs))); |
| 68 | |
| 69 | let op = PrepareQuantumROMState(nBitsPrecision, nCoeffs, nBitsIndices, keepCoeff, altIndex, [], Select, _, _, _); |
| 70 | let opWithSelect = PrepareQuantumROMState(nBitsPrecision, nCoeffs, nBitsIndices, keepCoeff, altIndex, [], _, _, _, _); |
| 71 | let (nIndexQubits, nGarbageQubits) = ArbitrarySuperpositionRegisterLengths(targetError, nCoeffs); |
| 72 | return PrepareArbitrarySuperposition(nIndexQubits, nGarbageQubits, op, opWithSelect); |
| 73 | } |
| 74 | |
| 75 | function MakePrepareArbitrarySuperpositionWithData(targetError : Double, coefficients : Double[], data: Bool[][]) : PrepareArbitrarySuperposition { |
| 76 | let nBitsPrecision = -Ceiling(Lg(0.5 * targetError)) + 1; |
| 77 | let positiveCoefficients = Mapped(AbsD, coefficients); |
| 78 | let (keepCoeff, altIndex) = DiscretizedProbabilityDistribution(nBitsPrecision, positiveCoefficients); |
| 79 | let nCoeffs = Length(positiveCoefficients); |
| 80 | let nBitsIndices = Ceiling(Lg(IntAsDouble(nCoeffs))); |
| 81 | |
| 82 | let op = PrepareQuantumROMState(nBitsPrecision, nCoeffs, nBitsIndices, keepCoeff, altIndex, data, Select, _, _, _); |
| 83 | let opWithSelect = PrepareQuantumROMState(nBitsPrecision, nCoeffs, nBitsIndices, keepCoeff, altIndex, data, _, _, _, _); |
| 84 | let (nIndexQubits, nGarbageQubits) = ArbitrarySuperpositionRegisterLengths(targetError, nCoeffs); |
| 85 | return PrepareArbitrarySuperposition(nIndexQubits, nGarbageQubits + Length(data[0]), op, opWithSelect); |
| 86 | } |
| 87 | |
| 88 | // -------------------------------------- // |
| 89 | // State preparation (private operations) // |
| 90 | // -------------------------------------- // |
| 91 | |
| 92 | internal function DecomposePowerOf2(number : Int) : (Int, Int) { |
| 93 | mutable pow = 0; |
| 94 | mutable factor = number; |
| 95 | |
| 96 | while factor % 2 == 0 { |
| 97 | set factor /= 2; |
| 98 | set pow += 1; |
| 99 | } |
| 100 | |
| 101 | (factor, pow) |
| 102 | } |
| 103 | |
| 104 | internal function ArbitrarySuperpositionRegisterLengths(targetError : Double, nCoefficients : Int) |
| 105 | : (Int, Int) { |
| 106 | Fact(targetError > 0.0, "targetError must be positive"); |
| 107 | Fact(nCoefficients > 0, "nCoefficients must be positive"); |
| 108 | |
| 109 | let nBitsPrecision = -Ceiling(Lg(0.5*targetError)) + 1; |
| 110 | let nIndexQubits = Ceiling(Lg(IntAsDouble(nCoefficients))); |
| 111 | let nGarbageQubits = nIndexQubits + 2 * nBitsPrecision + 1; |
| 112 | (nIndexQubits, nGarbageQubits) |
| 113 | } |
| 114 | |
| 115 | // Computes discretized probability distribution as described in Section 3 |
| 116 | // and Fig. 13 in [arXiv:1805.03662](https://arxiv.org/pdf/1805.03662.pdf) |
| 117 | internal function DiscretizedProbabilityDistribution(bitsPrecision: Int, coefficients: Double[]) |
| 118 | : (Int[], Int[]) { |
| 119 | let oneNorm = PNorm(1.0, coefficients); |
| 120 | let nCoefficients = Length(coefficients); |
| 121 | Fact(bitsPrecision <= 31, $"Bits of precision {bitsPrecision} unsupported. Max is 31."); |
| 122 | Fact(nCoefficients > 1, "Cannot prepare state with less than 2 coefficients."); |
| 123 | Fact(oneNorm != 0.0, "State must have at least one coefficient > 0"); |
| 124 | |
| 125 | let barHeight = 2 ^ bitsPrecision - 1; |
| 126 | |
| 127 | mutable altIndex = SequenceI(0, nCoefficients - 1); |
| 128 | mutable keepCoeff = Mapped( |
| 129 | coefficient -> Round((AbsD(coefficient) / oneNorm) * IntAsDouble(nCoefficients) * IntAsDouble(barHeight)), |
| 130 | coefficients |
| 131 | ); |
| 132 | |
| 133 | // Calculate difference between number of discretized bars vs. maximum |
| 134 | let bars = Fold((state, value) -> state + value - barHeight, 0, keepCoeff); |
| 135 | |
| 136 | // Uniformly distribute excess bars across coefficients. |
| 137 | for idx in 0..AbsI(bars) - 1 { |
| 138 | set keepCoeff w/= idx <- keepCoeff[idx] + (bars > 0 ? -1 | +1); |
| 139 | } |
| 140 | |
| 141 | mutable barSink = []; |
| 142 | mutable barSource = []; |
| 143 | |
| 144 | for idxCoeff in IndexRange(keepCoeff) { |
| 145 | if keepCoeff[idxCoeff] > barHeight { |
| 146 | set barSource += [idxCoeff]; |
| 147 | } elif keepCoeff[idxCoeff] < barHeight { |
| 148 | set barSink += [idxCoeff]; |
| 149 | } |
| 150 | } |
| 151 | |
| 152 | for rep in 0..nCoefficients * 10 { |
| 153 | if Length(barSink) > 0 and Length(barSource) > 0 { |
| 154 | let idxSink = Tail(barSink); |
| 155 | let idxSource = Tail(barSource); |
| 156 | set barSink = Most(barSink); |
| 157 | set barSource = Most(barSource); |
| 158 | |
| 159 | set keepCoeff w/= idxSource <- keepCoeff[idxSource] - barHeight + keepCoeff[idxSink]; |
| 160 | set altIndex w/= idxSink <- idxSource; |
| 161 | |
| 162 | if keepCoeff[idxSource] < barHeight { |
| 163 | set barSink += [idxSource]; |
| 164 | } elif keepCoeff[idxSource] > barHeight { |
| 165 | set barSource += [idxSource]; |
| 166 | } |
| 167 | } elif Length(barSource) > 0 { |
| 168 | let idxSource = Tail(barSource); |
| 169 | set barSource = Most(barSource); |
| 170 | set keepCoeff w/= idxSource <- barHeight; |
| 171 | } else { |
| 172 | return (keepCoeff, altIndex); |
| 173 | } |
| 174 | } |
| 175 | |
| 176 | return (keepCoeff, altIndex); |
| 177 | } |
| 178 | |
| 179 | // Used in QuantumROM implementation. |
| 180 | internal operation PrepareQuantumROMState( |
| 181 | nBitsPrecision: Int, nCoeffs: Int, nBitsIndices: Int, |
| 182 | keepCoeff: Int[], altIndex: Int[], data : Bool[][], |
| 183 | selectOperation: (Bool[][], Qubit[], Qubit[]) => Unit is Adj + Ctl, |
| 184 | indexRegister: Qubit[], dataQubits : Qubit[], garbageRegister: Qubit[] |
| 185 | ) |
| 186 | : Unit is Adj + Ctl { |
| 187 | let garbageIdx0 = nBitsIndices; |
| 188 | let garbageIdx1 = garbageIdx0 + nBitsPrecision; |
| 189 | let garbageIdx2 = garbageIdx1 + nBitsPrecision; |
| 190 | let garbageIdx3 = garbageIdx2 + 1; |
| 191 | |
| 192 | let altIndexRegister = garbageRegister[0..garbageIdx0 - 1]; |
| 193 | let keepCoeffRegister = garbageRegister[garbageIdx0..garbageIdx1 - 1]; |
| 194 | let uniformKeepCoeffRegister = garbageRegister[garbageIdx1..garbageIdx2 - 1]; |
| 195 | let flagQubit = garbageRegister[garbageIdx3 - 1]; |
| 196 | let dataRegister = dataQubits; |
| 197 | let altDataRegister = garbageRegister[garbageIdx3...]; |
| 198 | |
| 199 | // Create uniform superposition over index and alt coeff register. |
| 200 | PrepareUniformSuperposition(nCoeffs, indexRegister); |
| 201 | ApplyToEachCA(H, uniformKeepCoeffRegister); |
| 202 | |
| 203 | // Write bitstrings to altIndex and keepCoeff register. |
| 204 | let target = keepCoeffRegister + altIndexRegister + dataRegister + altDataRegister; |
| 205 | let selectData = MappedOverRange(idx -> |
| 206 | IntAsBoolArray(keepCoeff[idx], Length(keepCoeffRegister)) + |
| 207 | IntAsBoolArray(altIndex[idx], Length(altIndexRegister)) + |
| 208 | (IsEmpty(data) ? [] | data[idx] + data[altIndex[idx]]), 0..nCoeffs - 1); |
| 209 | selectOperation(selectData, indexRegister, target); |
| 210 | |
| 211 | // Perform comparison |
| 212 | ApplyIfGreaterLE(X, uniformKeepCoeffRegister, keepCoeffRegister, flagQubit); |
| 213 | |
| 214 | let indexRegisterSize = Length(indexRegister); |
| 215 | |
| 216 | // Swap in register based on comparison |
| 217 | let lhs = indexRegister + dataRegister; |
| 218 | let rhs = altIndexRegister + altDataRegister; |
| 219 | for i in IndexRange(lhs) { |
| 220 | Controlled SWAP([flagQubit], (lhs[i], rhs[i])); |
| 221 | } |
| 222 | } |
| 223 | } |
| 224 | |