microsoft/qdk
Publicmirrored from https://github.com/microsoft/qdkAvailable
compiler/qsc_eval/src/intrinsic/utils.rs
197lines · modecode
| 1 | // Copyright (c) Microsoft Corporation. |
| 2 | // Licensed under the MIT License. |
| 3 | |
| 4 | use std::collections::hash_map::Entry; |
| 5 | |
| 6 | use num_bigint::BigUint; |
| 7 | use num_complex::{Complex, Complex64}; |
| 8 | use num_traits::Zero; |
| 9 | use rustc_hash::{FxHashMap, FxHashSet}; |
| 10 | |
| 11 | /// Given a state and a set of qubits, split the state into two parts: the qubits to dump and the remaining qubits. |
| 12 | /// This function will return an error if the state is not separable using the provided qubit identifiers. |
| 13 | pub fn split_state( |
| 14 | qubits: &[usize], |
| 15 | state: &[(BigUint, Complex64)], |
| 16 | qubit_count: usize, |
| 17 | ) -> Result<Vec<(BigUint, Complex64)>, ()> { |
| 18 | // For an empty state, return an empty state. |
| 19 | // This handles cases where the underlying simulator doesn't track any quantum state. |
| 20 | if state.is_empty() { |
| 21 | return Ok(vec![]); |
| 22 | } |
| 23 | |
| 24 | let mut dump_state = FxHashMap::default(); |
| 25 | |
| 26 | // Compute the mask for the qubits to dump and the mask for the other qubits. |
| 27 | let (dump_mask, other_mask) = compute_mask(qubit_count, qubits); |
| 28 | |
| 29 | // Try to split out the state for the given qubits from the whole state, detecting any entanglement |
| 30 | // and returning an error if the qubits are not separable. |
| 31 | let dump_norm = collect_split_state(state, &dump_mask, &other_mask, &mut dump_state)?; |
| 32 | |
| 33 | let dump_norm = 1.0 / dump_norm.sqrt(); |
| 34 | let mut dump_state = dump_state |
| 35 | .into_iter() |
| 36 | .filter_map(|(label, val)| { |
| 37 | normalize_and_reorder(val, dump_norm, qubits, &label, qubit_count) |
| 38 | }) |
| 39 | .collect::<Vec<_>>(); |
| 40 | dump_state.sort_by(|(a, _), (b, _)| a.cmp(b)); |
| 41 | Ok(dump_state) |
| 42 | } |
| 43 | |
| 44 | /// From the qubit identifiers provided, compute the bit masks for the qubits to dump and the remaining qubits. |
| 45 | /// These masks can be applied to the state labels to separate the label into the two parts needed. |
| 46 | fn compute_mask(qubit_count: usize, qubits: &[usize]) -> (BigUint, BigUint) { |
| 47 | let mut dump_mask = BigUint::zero(); |
| 48 | let mut other_mask = BigUint::zero(); |
| 49 | for q in 0..qubit_count { |
| 50 | // Note that the qubit order is reversed to match the order of the qubits in the state. |
| 51 | if qubits.contains(&q) { |
| 52 | dump_mask.set_bit((qubit_count - q - 1) as u64, true); |
| 53 | } else { |
| 54 | other_mask.set_bit((qubit_count - q - 1) as u64, true); |
| 55 | } |
| 56 | } |
| 57 | (dump_mask, other_mask) |
| 58 | } |
| 59 | |
| 60 | /// Iterates through the given state and for each entry uses the mask to calculate what the separated labels would be |
| 61 | /// and finds the amplitude for each separated state. If the state is not separable, returns an error. |
| 62 | /// On success, the `dump_state` and `other_state` maps will be populated with the separated states, and the |
| 63 | /// function returns the accumulated norm of the dump state. |
| 64 | fn collect_split_state( |
| 65 | state: &[(BigUint, Complex64)], |
| 66 | dump_mask: &BigUint, |
| 67 | other_mask: &BigUint, |
| 68 | dump_state: &mut FxHashMap<BigUint, Complex64>, |
| 69 | ) -> Result<f64, ()> { |
| 70 | // To ensure consistent ordering, we iterate over the vector directly (returned from the simulator in a deterministic order), |
| 71 | // and not the map used for arbitrary lookup. |
| 72 | let mut state_iter = state.iter(); |
| 73 | let state_map = state.iter().cloned().collect::<FxHashMap<_, _>>(); |
| 74 | let (base_label, base_val) = state_iter.next().expect("state should never be empty"); |
| 75 | let dump_base_label = base_label & dump_mask; |
| 76 | let other_base_label = base_label & other_mask; |
| 77 | let mut dump_norm = base_val.norm().powi(2); |
| 78 | let mut other_state = FxHashSet::default(); |
| 79 | |
| 80 | dump_state.insert(dump_base_label.clone(), *base_val); |
| 81 | other_state.insert(other_base_label.clone()); |
| 82 | |
| 83 | for (curr_label, curr_val) in state_iter { |
| 84 | let dump_label = curr_label & dump_mask; |
| 85 | let other_label = curr_label & other_mask; |
| 86 | |
| 87 | // If either the state identified by the dump mask or the state identified by the other mask |
| 88 | // is None, that means it has zero amplitude and we can conclude the state is not separable. |
| 89 | let Some(dump_val) = state_map.get(&(&dump_label | &other_base_label)) else { |
| 90 | return Err(()); |
| 91 | }; |
| 92 | let Some(other_val) = state_map.get(&(&dump_base_label | &other_label)) else { |
| 93 | return Err(()); |
| 94 | }; |
| 95 | |
| 96 | if !(dump_val * other_val - base_val * curr_val) |
| 97 | .norm() |
| 98 | .is_nearly_zero() |
| 99 | { |
| 100 | // Coefficients are not equal, so the state is not separable. |
| 101 | return Err(()); |
| 102 | } |
| 103 | |
| 104 | if let Entry::Vacant(entry) = dump_state.entry(dump_label) { |
| 105 | let amplitude = *curr_val; |
| 106 | let norm = amplitude.norm().powi(2); |
| 107 | if !norm.is_nearly_zero() { |
| 108 | entry.insert(amplitude); |
| 109 | dump_norm += norm; |
| 110 | } |
| 111 | } |
| 112 | if !(curr_val / dump_val).norm().powi(2).is_nearly_zero() { |
| 113 | other_state.insert(other_label); |
| 114 | } |
| 115 | } |
| 116 | |
| 117 | // If the product of the collected states is not equal to the total number of input states, then that |
| 118 | // implies some states are zero amplitude that would have to be non-zero for the state to be separable. |
| 119 | if state.len() != dump_state.len() * other_state.len() { |
| 120 | return Err(()); |
| 121 | } |
| 122 | Ok(dump_norm) |
| 123 | } |
| 124 | |
| 125 | /// Given a dump state amplitude, the normalization factor, the qubits to dump, the label, and the qubit count, |
| 126 | /// normalize the amplitude and reorder the label to match the provided qubit order. |
| 127 | /// Specifically, qubits in the requested array may not be in the same allocation order that is used in the state |
| 128 | /// labels, so the bits in the label must be reordered to match the qubit order. |
| 129 | fn normalize_and_reorder( |
| 130 | val: Complex64, |
| 131 | dump_norm: f64, |
| 132 | qubits: &[usize], |
| 133 | label: &BigUint, |
| 134 | qubit_count: usize, |
| 135 | ) -> Option<(BigUint, Complex64)> { |
| 136 | // Normalize the dump state by the collected factor. |
| 137 | let new_val = val * dump_norm; |
| 138 | // Drop any zero amplitude states. |
| 139 | if new_val.is_nearly_zero() { |
| 140 | None |
| 141 | } else { |
| 142 | // Reorder the bits in the label to match the provided qubit order. |
| 143 | let mut new_label = BigUint::zero(); |
| 144 | for (i, q) in qubits.iter().enumerate() { |
| 145 | // Note that the qubit order is reversed to match the order of the qubits in the state. |
| 146 | if label.bit((qubit_count - *q - 1) as u64) { |
| 147 | new_label.set_bit((qubits.len() - i - 1) as u64, true); |
| 148 | } |
| 149 | } |
| 150 | |
| 151 | Some((new_label, new_val)) |
| 152 | } |
| 153 | } |
| 154 | |
| 155 | trait NearlyZero { |
| 156 | fn is_nearly_zero(&self) -> bool; |
| 157 | } |
| 158 | |
| 159 | impl NearlyZero for f64 { |
| 160 | fn is_nearly_zero(&self) -> bool { |
| 161 | self.abs() <= 1e-10 |
| 162 | } |
| 163 | } |
| 164 | |
| 165 | impl<T> NearlyZero for Complex<T> |
| 166 | where |
| 167 | T: NearlyZero, |
| 168 | { |
| 169 | fn is_nearly_zero(&self) -> bool { |
| 170 | self.re.is_nearly_zero() && self.im.is_nearly_zero() |
| 171 | } |
| 172 | } |
| 173 | |
| 174 | pub(crate) fn state_to_matrix( |
| 175 | state: Vec<(BigUint, Complex64)>, |
| 176 | qubit_count: usize, |
| 177 | ) -> Vec<Vec<Complex64>> { |
| 178 | let state: FxHashMap<BigUint, Complex<f64>> = state.into_iter().collect(); |
| 179 | let mut matrix = Vec::new(); |
| 180 | let num_entries: usize = 1 << qubit_count; |
| 181 | #[allow(clippy::cast_precision_loss)] |
| 182 | let factor = (num_entries as f64).sqrt(); |
| 183 | for i in 0..num_entries { |
| 184 | let mut row = Vec::new(); |
| 185 | for j in 0..num_entries { |
| 186 | let key = BigUint::from(i * num_entries + j); |
| 187 | let val = match state.get(&key) { |
| 188 | Some(val) => val * factor, |
| 189 | None => Complex::zero(), |
| 190 | }; |
| 191 | row.push(val); |
| 192 | } |
| 193 | matrix.push(row); |
| 194 | } |
| 195 | |
| 196 | matrix |
| 197 | } |
| 198 | |