microsoft/qdk
Publicmirrored from https://github.com/microsoft/qdkAvailable
compiler/qsc_circuit/src/builder.rs
536lines · modecode
| 1 | // Copyright (c) Microsoft Corporation. |
| 2 | // Licensed under the MIT License. |
| 3 | |
| 4 | use crate::{ |
| 5 | circuit::{Circuit, Operation, Register}, |
| 6 | Config, |
| 7 | }; |
| 8 | use num_bigint::BigUint; |
| 9 | use num_complex::Complex; |
| 10 | use qsc_data_structures::index_map::IndexMap; |
| 11 | use qsc_eval::{backend::Backend, val::Value}; |
| 12 | use std::{fmt::Write, mem::take, rc::Rc}; |
| 13 | |
| 14 | /// Backend implementation that builds a circuit representation. |
| 15 | pub struct Builder { |
| 16 | circuit: Circuit, |
| 17 | config: Config, |
| 18 | remapper: Remapper, |
| 19 | } |
| 20 | |
| 21 | impl Backend for Builder { |
| 22 | type ResultType = usize; |
| 23 | |
| 24 | fn ccx(&mut self, ctl0: usize, ctl1: usize, q: usize) { |
| 25 | let ctl0 = self.map(ctl0); |
| 26 | let ctl1 = self.map(ctl1); |
| 27 | let q = self.map(q); |
| 28 | self.push_gate(controlled_gate("X", [ctl0, ctl1], [q])); |
| 29 | } |
| 30 | |
| 31 | fn cx(&mut self, ctl: usize, q: usize) { |
| 32 | let ctl = self.map(ctl); |
| 33 | let q = self.map(q); |
| 34 | self.push_gate(controlled_gate("X", [ctl], [q])); |
| 35 | } |
| 36 | |
| 37 | fn cy(&mut self, ctl: usize, q: usize) { |
| 38 | let ctl = self.map(ctl); |
| 39 | let q = self.map(q); |
| 40 | self.push_gate(controlled_gate("Y", [ctl], [q])); |
| 41 | } |
| 42 | |
| 43 | fn cz(&mut self, ctl: usize, q: usize) { |
| 44 | let ctl = self.map(ctl); |
| 45 | let q = self.map(q); |
| 46 | self.push_gate(controlled_gate("Z", [ctl], [q])); |
| 47 | } |
| 48 | |
| 49 | fn h(&mut self, q: usize) { |
| 50 | let q = self.map(q); |
| 51 | self.push_gate(gate("H", [q])); |
| 52 | } |
| 53 | |
| 54 | fn m(&mut self, q: usize) -> Self::ResultType { |
| 55 | if self.config.base_profile { |
| 56 | // defer the measurement and reset the qubit |
| 57 | self.remapper.mreset(q) |
| 58 | } else { |
| 59 | let mapped_q = self.map(q); |
| 60 | // In the Circuit schema, result id is per-qubit |
| 61 | let res_id = self.num_measurements_for_qubit(mapped_q); |
| 62 | let id = self.remapper.m(q); |
| 63 | |
| 64 | self.push_gate(measurement_gate(mapped_q.0, res_id)); |
| 65 | id |
| 66 | } |
| 67 | } |
| 68 | |
| 69 | fn mresetz(&mut self, q: usize) -> Self::ResultType { |
| 70 | if self.config.base_profile { |
| 71 | // defer the measurement |
| 72 | self.remapper.mreset(q) |
| 73 | } else { |
| 74 | let mapped_q = self.map(q); |
| 75 | // In the Circuit schema, result id is per-qubit |
| 76 | let res_id = self.num_measurements_for_qubit(mapped_q); |
| 77 | // We don't actually need the Remapper since we're not |
| 78 | // remapping any qubits, but it's handy for keeping track of measurements |
| 79 | let id = self.remapper.m(q); |
| 80 | |
| 81 | // Ideally MResetZ would be atomic but we don't currently have |
| 82 | // a way to visually represent that. So decompose it into |
| 83 | // a measurement and a reset gate. |
| 84 | self.push_gate(measurement_gate(mapped_q.0, res_id)); |
| 85 | self.push_gate(gate(KET_ZERO, [mapped_q])); |
| 86 | id |
| 87 | } |
| 88 | } |
| 89 | |
| 90 | fn reset(&mut self, q: usize) { |
| 91 | if self.config.base_profile { |
| 92 | self.remapper.reset(q); |
| 93 | } else { |
| 94 | let mapped_q = self.map(q); |
| 95 | self.push_gate(gate(KET_ZERO, [mapped_q])); |
| 96 | } |
| 97 | } |
| 98 | |
| 99 | fn rx(&mut self, theta: f64, q: usize) { |
| 100 | let q = self.map(q); |
| 101 | self.push_gate(rotation_gate("rx", theta, [q])); |
| 102 | } |
| 103 | |
| 104 | fn rxx(&mut self, theta: f64, q0: usize, q1: usize) { |
| 105 | let q0 = self.map(q0); |
| 106 | let q1 = self.map(q1); |
| 107 | self.push_gate(rotation_gate("rxx", theta, [q0, q1])); |
| 108 | } |
| 109 | |
| 110 | fn ry(&mut self, theta: f64, q: usize) { |
| 111 | let q = self.map(q); |
| 112 | self.push_gate(rotation_gate("ry", theta, [q])); |
| 113 | } |
| 114 | |
| 115 | fn ryy(&mut self, theta: f64, q0: usize, q1: usize) { |
| 116 | let q0 = self.map(q0); |
| 117 | let q1 = self.map(q1); |
| 118 | self.push_gate(rotation_gate("ryy", theta, [q0, q1])); |
| 119 | } |
| 120 | |
| 121 | fn rz(&mut self, theta: f64, q: usize) { |
| 122 | let q = self.map(q); |
| 123 | self.push_gate(rotation_gate("rz", theta, [q])); |
| 124 | } |
| 125 | |
| 126 | fn rzz(&mut self, theta: f64, q0: usize, q1: usize) { |
| 127 | let q0 = self.map(q0); |
| 128 | let q1 = self.map(q1); |
| 129 | self.push_gate(rotation_gate("rzz", theta, [q0, q1])); |
| 130 | } |
| 131 | |
| 132 | fn sadj(&mut self, q: usize) { |
| 133 | let q = self.map(q); |
| 134 | self.push_gate(adjoint_gate("S", [q])); |
| 135 | } |
| 136 | |
| 137 | fn s(&mut self, q: usize) { |
| 138 | let q = self.map(q); |
| 139 | self.push_gate(gate("S", [q])); |
| 140 | } |
| 141 | |
| 142 | fn swap(&mut self, q0: usize, q1: usize) { |
| 143 | let q0 = self.map(q0); |
| 144 | let q1 = self.map(q1); |
| 145 | self.push_gate(gate("SWAP", [q0, q1])); |
| 146 | } |
| 147 | |
| 148 | fn tadj(&mut self, q: usize) { |
| 149 | let q = self.map(q); |
| 150 | self.push_gate(adjoint_gate("T", [q])); |
| 151 | } |
| 152 | |
| 153 | fn t(&mut self, q: usize) { |
| 154 | let q = self.map(q); |
| 155 | self.push_gate(gate("T", [q])); |
| 156 | } |
| 157 | |
| 158 | fn x(&mut self, q: usize) { |
| 159 | let q = self.map(q); |
| 160 | self.push_gate(gate("X", [q])); |
| 161 | } |
| 162 | |
| 163 | fn y(&mut self, q: usize) { |
| 164 | let q = self.map(q); |
| 165 | self.push_gate(gate("Y", [q])); |
| 166 | } |
| 167 | |
| 168 | fn z(&mut self, q: usize) { |
| 169 | let q = self.map(q); |
| 170 | self.push_gate(gate("Z", [q])); |
| 171 | } |
| 172 | |
| 173 | fn qubit_allocate(&mut self) -> usize { |
| 174 | self.remapper.qubit_allocate() |
| 175 | } |
| 176 | |
| 177 | fn qubit_release(&mut self, q: usize) -> bool { |
| 178 | self.remapper.qubit_release(q); |
| 179 | true |
| 180 | } |
| 181 | |
| 182 | fn qubit_swap_id(&mut self, q0: usize, q1: usize) { |
| 183 | self.remapper.swap(q0, q1); |
| 184 | } |
| 185 | |
| 186 | fn capture_quantum_state(&mut self) -> (Vec<(BigUint, Complex<f64>)>, usize) { |
| 187 | (Vec::new(), 0) |
| 188 | } |
| 189 | |
| 190 | fn qubit_is_zero(&mut self, _q: usize) -> bool { |
| 191 | // We don't simulate quantum execution here. So we don't know if the qubit |
| 192 | // is zero or not. Returning true avoids potential panics. |
| 193 | true |
| 194 | } |
| 195 | |
| 196 | fn custom_intrinsic(&mut self, name: &str, arg: Value) -> Option<Result<Value, String>> { |
| 197 | // The qubit arguments are treated as the targets for custom gates. |
| 198 | // Any remaining arguments will be kept in the display_args field |
| 199 | // to be shown as part of the gate label when the circuit is rendered. |
| 200 | let (qubit_args, classical_args) = self.split_qubit_args(arg); |
| 201 | |
| 202 | self.push_gate(custom_gate( |
| 203 | name, |
| 204 | &qubit_args, |
| 205 | if classical_args.is_empty() { |
| 206 | None |
| 207 | } else { |
| 208 | Some(classical_args) |
| 209 | }, |
| 210 | )); |
| 211 | |
| 212 | match name { |
| 213 | // Special case this known intrinsic to match the simulator |
| 214 | // behavior, so that our samples will work |
| 215 | "BeginEstimateCaching" => Some(Ok(Value::Bool(true))), |
| 216 | _ => Some(Ok(Value::unit())), |
| 217 | } |
| 218 | } |
| 219 | } |
| 220 | |
| 221 | impl Builder { |
| 222 | #[must_use] |
| 223 | pub fn new(config: Config) -> Self { |
| 224 | Builder { |
| 225 | circuit: Circuit::default(), |
| 226 | config, |
| 227 | remapper: Remapper::default(), |
| 228 | } |
| 229 | } |
| 230 | |
| 231 | #[must_use] |
| 232 | pub fn snapshot(&self) -> Circuit { |
| 233 | let circuit = self.circuit.clone(); |
| 234 | self.finish_circuit(circuit) |
| 235 | } |
| 236 | |
| 237 | #[must_use] |
| 238 | pub fn finish(mut self) -> Circuit { |
| 239 | let circuit = take(&mut self.circuit); |
| 240 | self.finish_circuit(circuit) |
| 241 | } |
| 242 | |
| 243 | fn map(&mut self, qubit: usize) -> WireId { |
| 244 | self.remapper.map(qubit) |
| 245 | } |
| 246 | |
| 247 | fn push_gate(&mut self, gate: Operation) { |
| 248 | self.circuit.operations.push(gate); |
| 249 | } |
| 250 | |
| 251 | fn num_measurements_for_qubit(&self, qubit: WireId) -> usize { |
| 252 | self.remapper |
| 253 | .qubit_measurement_counts |
| 254 | .get(qubit) |
| 255 | .copied() |
| 256 | .unwrap_or_default() |
| 257 | } |
| 258 | |
| 259 | fn finish_circuit(&self, mut circuit: Circuit) -> Circuit { |
| 260 | // add deferred measurements |
| 261 | if self.config.base_profile { |
| 262 | for (qubit, _) in &self.remapper.qubit_measurement_counts { |
| 263 | // guaranteed one measurement per qubit, so result is always 0 |
| 264 | circuit.operations.push(measurement_gate(qubit.0, 0)); |
| 265 | } |
| 266 | } |
| 267 | |
| 268 | // add qubit declarations |
| 269 | for i in 0..self.remapper.num_qubits() { |
| 270 | let num_measurements = self.num_measurements_for_qubit(WireId(i)); |
| 271 | circuit.qubits.push(crate::circuit::Qubit { |
| 272 | id: i, |
| 273 | num_children: num_measurements, |
| 274 | }); |
| 275 | } |
| 276 | |
| 277 | circuit |
| 278 | } |
| 279 | |
| 280 | /// Splits the qubit arguments from classical arguments so that the qubits |
| 281 | /// can be treated as the targets for custom gates. |
| 282 | /// The classical arguments get formatted into a comma-separated list. |
| 283 | fn split_qubit_args(&mut self, arg: Value) -> (Vec<WireId>, String) { |
| 284 | let arg = if let Value::Tuple(vals) = arg { |
| 285 | vals |
| 286 | } else { |
| 287 | // Single arguments are not passed as tuples, wrap in an array |
| 288 | Rc::new([arg]) |
| 289 | }; |
| 290 | let mut qubits = vec![]; |
| 291 | let mut classical_args = String::new(); |
| 292 | self.push_vals(&arg, &mut qubits, &mut classical_args); |
| 293 | (qubits, classical_args) |
| 294 | } |
| 295 | |
| 296 | /// Pushes all qubit values into `qubits`, and formats all classical values into `classical_args`. |
| 297 | fn push_val(&mut self, arg: &Value, qubits: &mut Vec<WireId>, classical_args: &mut String) { |
| 298 | match arg { |
| 299 | Value::Array(vals) => { |
| 300 | self.push_list::<'[', ']'>(vals, qubits, classical_args); |
| 301 | } |
| 302 | Value::Tuple(vals) => { |
| 303 | self.push_list::<'(', ')'>(vals, qubits, classical_args); |
| 304 | } |
| 305 | Value::Qubit(q) => { |
| 306 | qubits.push(self.map(q.0)); |
| 307 | } |
| 308 | v => { |
| 309 | let _ = write!(classical_args, "{v}"); |
| 310 | } |
| 311 | } |
| 312 | qubits.sort_unstable_by_key(|q| q.0); |
| 313 | qubits.dedup_by_key(|q| q.0); |
| 314 | } |
| 315 | |
| 316 | /// Pushes all qubit values into `qubits`, and formats all |
| 317 | /// classical values into `classical_args` as a list. |
| 318 | fn push_list<const OPEN: char, const CLOSE: char>( |
| 319 | &mut self, |
| 320 | vals: &[Value], |
| 321 | qubits: &mut Vec<WireId>, |
| 322 | classical_args: &mut String, |
| 323 | ) { |
| 324 | classical_args.push(OPEN); |
| 325 | let start = classical_args.len(); |
| 326 | self.push_vals(vals, qubits, classical_args); |
| 327 | if classical_args.len() > start { |
| 328 | classical_args.push(CLOSE); |
| 329 | } else { |
| 330 | classical_args.pop(); |
| 331 | } |
| 332 | } |
| 333 | |
| 334 | /// Pushes all qubit values into `qubits`, and formats all |
| 335 | /// classical values into `classical_args` as comma-separated values. |
| 336 | fn push_vals(&mut self, vals: &[Value], qubits: &mut Vec<WireId>, classical_args: &mut String) { |
| 337 | let mut any = false; |
| 338 | for v in vals.iter() { |
| 339 | let start = classical_args.len(); |
| 340 | self.push_val(v, qubits, classical_args); |
| 341 | if classical_args.len() > start { |
| 342 | any = true; |
| 343 | classical_args.push_str(", "); |
| 344 | } |
| 345 | } |
| 346 | if any { |
| 347 | // remove trailing comma |
| 348 | classical_args.pop(); |
| 349 | classical_args.pop(); |
| 350 | } |
| 351 | } |
| 352 | } |
| 353 | |
| 354 | /// Provides support for qubit id allocation, measurement and |
| 355 | /// reset operations for Base Profile targets. |
| 356 | /// |
| 357 | /// Since qubit reuse is disallowed, a mapping is maintained |
| 358 | /// from allocated qubit ids to hardware qubit ids. Each time |
| 359 | /// a qubit is reset, it is remapped to a fresh hardware qubit. |
| 360 | /// |
| 361 | /// Note that even though qubit reset & reuse is disallowed, |
| 362 | /// qubit ids are still reused for new allocations. |
| 363 | /// Measurements are tracked and deferred. |
| 364 | #[derive(Default)] |
| 365 | struct Remapper { |
| 366 | next_meas_id: usize, |
| 367 | next_qubit_id: usize, |
| 368 | next_qubit_wire_id: WireId, |
| 369 | qubit_map: IndexMap<usize, WireId>, |
| 370 | qubit_measurement_counts: IndexMap<WireId, usize>, |
| 371 | } |
| 372 | |
| 373 | impl Remapper { |
| 374 | fn map(&mut self, qubit: usize) -> WireId { |
| 375 | if let Some(mapped) = self.qubit_map.get(qubit) { |
| 376 | *mapped |
| 377 | } else { |
| 378 | let mapped = self.next_qubit_wire_id; |
| 379 | self.next_qubit_wire_id.0 += 1; |
| 380 | self.qubit_map.insert(qubit, mapped); |
| 381 | mapped |
| 382 | } |
| 383 | } |
| 384 | |
| 385 | fn m(&mut self, q: usize) -> usize { |
| 386 | let mapped_q = self.map(q); |
| 387 | let id = self.get_meas_id(); |
| 388 | match self.qubit_measurement_counts.get_mut(mapped_q) { |
| 389 | Some(count) => *count += 1, |
| 390 | None => { |
| 391 | self.qubit_measurement_counts.insert(mapped_q, 1); |
| 392 | } |
| 393 | } |
| 394 | id |
| 395 | } |
| 396 | |
| 397 | fn mreset(&mut self, q: usize) -> usize { |
| 398 | let id = self.m(q); |
| 399 | self.reset(q); |
| 400 | id |
| 401 | } |
| 402 | |
| 403 | fn reset(&mut self, q: usize) { |
| 404 | self.qubit_map.remove(q); |
| 405 | } |
| 406 | |
| 407 | fn qubit_allocate(&mut self) -> usize { |
| 408 | let id = self.next_qubit_id; |
| 409 | self.next_qubit_id += 1; |
| 410 | let _ = self.map(id); |
| 411 | id |
| 412 | } |
| 413 | |
| 414 | fn qubit_release(&mut self, _q: usize) { |
| 415 | self.next_qubit_id -= 1; |
| 416 | } |
| 417 | |
| 418 | fn swap(&mut self, q0: usize, q1: usize) { |
| 419 | let q0_mapped = self.map(q0); |
| 420 | let q1_mapped = self.map(q1); |
| 421 | self.qubit_map.insert(q0, q1_mapped); |
| 422 | self.qubit_map.insert(q1, q0_mapped); |
| 423 | } |
| 424 | |
| 425 | #[must_use] |
| 426 | fn num_qubits(&self) -> usize { |
| 427 | self.next_qubit_wire_id.0 |
| 428 | } |
| 429 | |
| 430 | #[must_use] |
| 431 | fn get_meas_id(&mut self) -> usize { |
| 432 | let id = self.next_meas_id; |
| 433 | self.next_meas_id += 1; |
| 434 | id |
| 435 | } |
| 436 | } |
| 437 | |
| 438 | #[derive(Copy, Clone, Default)] |
| 439 | struct WireId(pub usize); |
| 440 | |
| 441 | impl From<usize> for WireId { |
| 442 | fn from(id: usize) -> Self { |
| 443 | WireId(id) |
| 444 | } |
| 445 | } |
| 446 | |
| 447 | impl From<WireId> for usize { |
| 448 | fn from(id: WireId) -> Self { |
| 449 | id.0 |
| 450 | } |
| 451 | } |
| 452 | |
| 453 | #[allow(clippy::unicode_not_nfc)] |
| 454 | static KET_ZERO: &str = "|0〉"; |
| 455 | |
| 456 | fn gate<const N: usize>(name: &str, targets: [WireId; N]) -> Operation { |
| 457 | Operation { |
| 458 | gate: name.into(), |
| 459 | display_args: None, |
| 460 | is_controlled: false, |
| 461 | is_adjoint: false, |
| 462 | is_measurement: false, |
| 463 | controls: vec![], |
| 464 | targets: targets.iter().map(|q| Register::quantum(q.0)).collect(), |
| 465 | children: vec![], |
| 466 | } |
| 467 | } |
| 468 | |
| 469 | fn adjoint_gate<const N: usize>(name: &str, targets: [WireId; N]) -> Operation { |
| 470 | Operation { |
| 471 | gate: name.into(), |
| 472 | display_args: None, |
| 473 | is_controlled: false, |
| 474 | is_adjoint: true, |
| 475 | is_measurement: false, |
| 476 | controls: vec![], |
| 477 | targets: targets.iter().map(|q| Register::quantum(q.0)).collect(), |
| 478 | children: vec![], |
| 479 | } |
| 480 | } |
| 481 | |
| 482 | fn controlled_gate<const M: usize, const N: usize>( |
| 483 | name: &str, |
| 484 | controls: [WireId; M], |
| 485 | targets: [WireId; N], |
| 486 | ) -> Operation { |
| 487 | Operation { |
| 488 | gate: name.into(), |
| 489 | display_args: None, |
| 490 | is_controlled: true, |
| 491 | is_adjoint: false, |
| 492 | is_measurement: false, |
| 493 | controls: controls.iter().map(|q| Register::quantum(q.0)).collect(), |
| 494 | targets: targets.iter().map(|q| Register::quantum(q.0)).collect(), |
| 495 | children: vec![], |
| 496 | } |
| 497 | } |
| 498 | |
| 499 | fn measurement_gate(qubit: usize, result: usize) -> Operation { |
| 500 | Operation { |
| 501 | gate: "Measure".into(), |
| 502 | display_args: None, |
| 503 | is_controlled: false, |
| 504 | is_adjoint: false, |
| 505 | is_measurement: true, |
| 506 | controls: vec![Register::quantum(qubit)], |
| 507 | targets: vec![Register::classical(qubit, result)], |
| 508 | children: vec![], |
| 509 | } |
| 510 | } |
| 511 | |
| 512 | fn rotation_gate<const N: usize>(name: &str, theta: f64, targets: [WireId; N]) -> Operation { |
| 513 | Operation { |
| 514 | gate: name.into(), |
| 515 | display_args: Some(format!("{theta:.4}")), |
| 516 | is_controlled: false, |
| 517 | is_adjoint: false, |
| 518 | is_measurement: false, |
| 519 | controls: vec![], |
| 520 | targets: targets.iter().map(|q| Register::quantum(q.0)).collect(), |
| 521 | children: vec![], |
| 522 | } |
| 523 | } |
| 524 | |
| 525 | fn custom_gate(name: &str, targets: &[WireId], display_args: Option<String>) -> Operation { |
| 526 | Operation { |
| 527 | gate: name.into(), |
| 528 | display_args, |
| 529 | is_controlled: false, |
| 530 | is_adjoint: false, |
| 531 | is_measurement: false, |
| 532 | controls: vec![], |
| 533 | targets: targets.iter().map(|q| Register::quantum(q.0)).collect(), |
| 534 | children: vec![], |
| 535 | } |
| 536 | } |
| 537 | |