GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored fromhttps://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
cesarzc/ssa-panic

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/compiler/qsc_eval/src

compiler/qsc_eval/src/state.rs

527lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4#[cfg(test)]
5mod tests;
6
7use num_bigint::BigUint;
8use num_complex::{Complex, Complex64};
9use std::fmt::Write;
10
11#[must_use]
12pub fn format_state_id(id: &BigUint, qubit_count: usize) -> String {
13 format!("|{}⟩", fmt_basis_state_label(id, qubit_count))
14}
15
16#[must_use]
17pub fn get_phase(c: &Complex<f64>) -> f64 {
18 f64::atan2(c.im, c.re)
19}
20
21#[must_use]
22pub fn fmt_complex(c: &Complex<f64>) -> String {
23 // Format -0 as 0
24 // Also using Unicode Minus Sign instead of ASCII Hyphen-Minus
25 // and Unicode Mathematical Italic Small I instead of ASCII i.
26 format!(
27 "{}{:.4}{}{:.4}𝑖",
28 if c.re <= -0.00005 { "−" } else { "" },
29 c.re.abs(),
30 if c.im <= -0.00005 { "−" } else { "+" },
31 c.im.abs()
32 )
33}
34
35#[must_use]
36pub fn fmt_basis_state_label(id: &BigUint, qubit_count: usize) -> String {
37 // This will generate a bit string that shows the qubits in the order
38 // of allocation, left to right.
39 format!("{:0>qubit_count$}", id.to_str_radix(2))
40}
41
42#[must_use]
43fn is_significant(x: f64) -> bool {
44 x.abs() > 1e-9
45}
46
47#[must_use]
48fn is_fractional_part_significant(x: f64) -> bool {
49 is_significant(x - x.round())
50}
51
52/// Represents a non-zero rational number in the form ``numerator/denominator``
53/// Sign of the number is separated for easier composition and rendering
54#[derive(Copy, Clone, Debug)]
55struct RationalNumber {
56 sign: i64, // 1 if the number is positive, -1 if negative
57 numerator: i64, // Positive numerator
58 denominator: i64, // Positive denominator
59}
60
61impl RationalNumber {
62 fn new(numerator: i64, denominator: i64) -> Self {
63 Self {
64 sign: numerator.signum() * denominator.signum(),
65 numerator: numerator.abs(),
66 denominator: denominator.abs(),
67 }
68 }
69
70 fn abs(&self) -> Self {
71 Self {
72 sign: self.sign.abs(),
73 numerator: self.numerator,
74 denominator: self.denominator,
75 }
76 }
77
78 const DENOMINATORS: [i64; 36] = [
79 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36,
80 40, 42, 45, 48, 49, 50, 54, 56, 60, 63, 64,
81 ];
82
83 /// Try to recognize a float number as a "nice" rational.
84 fn recognize(x: f64) -> Option<Self> {
85 for denominator in Self::DENOMINATORS {
86 #[allow(clippy::cast_precision_loss)] // We only use fixes set of denominators
87 let numerator: f64 = x * (denominator as f64);
88 if numerator.abs() <= 100.0 && !is_fractional_part_significant(numerator) {
89 #[allow(clippy::cast_possible_truncation)] // We only allow small numerators
90 let rounded_numerator: i64 = numerator.round() as i64;
91 return Some(Self::new(rounded_numerator, denominator));
92 }
93 }
94 None
95 }
96}
97
98/// Represents a non-zero algebraic number in the form ``fraction·√root``,
99/// Sign of the number is separated for easier composition and rendering
100#[derive(Debug)]
101struct AlgebraicNumber {
102 sign: i64, // 1 if the number is positive, -1 if negative
103 fraction: RationalNumber, // Positive rational number numerator/denominator
104 root: i64, // Component under square root
105}
106
107impl AlgebraicNumber {
108 fn new(fraction: &RationalNumber, root: i64) -> Self {
109 Self {
110 sign: fraction.sign,
111 fraction: fraction.abs(),
112 root,
113 }
114 }
115
116 const ROOTS: [i64; 6] = [1, 2, 3, 5, 6, 7];
117
118 /// Try to recognize a float number as a "nice" algebraic.
119 fn recognize(x: f64) -> Option<Self> {
120 for root in Self::ROOTS {
121 #[allow(clippy::cast_precision_loss)] // We only use fixes set of roots
122 let divided_by_root: f64 = x / (root as f64).sqrt();
123 if let Some(fraction) = RationalNumber::recognize(divided_by_root) {
124 return Some(Self::new(&fraction, root));
125 }
126 }
127 None
128 }
129}
130
131/// Represents a non-zero decimal number as an ``f64`` floating point value.
132/// Sign of the number is separated for easier composition and rendering
133#[derive(Debug)]
134struct DecimalNumber {
135 sign: i64, // 1 if the number is positive, -1 if negative
136 value: f64, // Positive floating point value
137}
138
139impl DecimalNumber {
140 fn new(value: f64) -> Self {
141 Self {
142 sign: if value >= 0.0 { 1 } else { -1 },
143 value: value.abs(),
144 }
145 }
146
147 // Tries to recognize a decimal number and always succeeds.
148 fn recognize(x: f64) -> Self {
149 Self::new(x)
150 }
151}
152
153/// Represents a real number, which can be algebraic, decimal or zero.
154#[derive(Debug)]
155enum RealNumber {
156 Algebraic(AlgebraicNumber),
157 Decimal(DecimalNumber),
158 Zero,
159}
160
161impl RealNumber {
162 fn sign(&self) -> i64 {
163 match self {
164 Self::Algebraic(algebraic) => algebraic.sign,
165 Self::Decimal(decimal) => decimal.sign,
166 Self::Zero => 0,
167 }
168 }
169
170 fn negate(&self) -> Self {
171 match self {
172 Self::Algebraic(algebraic) => Self::Algebraic(AlgebraicNumber {
173 sign: -algebraic.sign,
174 fraction: algebraic.fraction,
175 root: algebraic.root,
176 }),
177 Self::Decimal(decimal) => Self::Decimal(DecimalNumber {
178 sign: -decimal.sign,
179 value: decimal.value,
180 }),
181 Self::Zero => Self::Zero,
182 }
183 }
184
185 fn abs(&self) -> Self {
186 match self {
187 Self::Algebraic(algebraic) => Self::Algebraic(AlgebraicNumber {
188 sign: 1,
189 fraction: algebraic.fraction,
190 root: algebraic.root,
191 }),
192 Self::Decimal(decimal) => Self::Decimal(DecimalNumber {
193 sign: 1,
194 value: decimal.value,
195 }),
196 Self::Zero => Self::Zero,
197 }
198 }
199
200 /// Try to recognize a real number as zero, algebraic, or decimal if all else fails.
201 fn recognize(x: f64) -> Self {
202 if !is_significant(x) {
203 Self::Zero
204 } else if let Some(algebraic_number) = AlgebraicNumber::recognize(x) {
205 Self::Algebraic(algebraic_number)
206 } else {
207 Self::Decimal(DecimalNumber::recognize(x))
208 }
209 }
210}
211
212/// Represents a non-zero complex numbers in the polar form: ``coefficient·𝒆^(𝝅·𝒊·phase_multiplier)``
213/// Sign of the number is separated for easier composition and rendering
214#[derive(Debug)]
215struct PolarForm {
216 sign: i64, // For this form the sign is always 1
217 magnitude: AlgebraicNumber, // magnitude of the number
218 phase_multiplier: RationalNumber, // to be multiplied by 𝝅·𝒊 to get phase
219}
220
221impl PolarForm {
222 fn new(magnitude: &RationalNumber, pi_num: i64, pi_den: i64) -> Self {
223 Self {
224 sign: 1,
225 magnitude: AlgebraicNumber::new(magnitude, 1),
226 phase_multiplier: RationalNumber::new(pi_num, pi_den),
227 }
228 }
229
230 const PI_FRACTIONS: [(i64, i64); 16] = [
231 (1, 3),
232 (2, 3),
233 (1, 4),
234 (3, 4),
235 (1, 8),
236 (3, 8),
237 (5, 8),
238 (7, 8),
239 (1, 16),
240 (3, 16),
241 (5, 16),
242 (7, 16),
243 (9, 16),
244 (11, 16),
245 (13, 16),
246 (15, 16),
247 ];
248
249 /// Try to recognize a complex number and represent it in the polar form.
250 fn recognize(re: f64, im: f64) -> Option<Self> {
251 for (pi_num, pi_den) in Self::PI_FRACTIONS {
252 #[allow(clippy::cast_precision_loss)] // We only use fixes set of fractions
253 let angle: f64 = std::f64::consts::PI * (pi_num as f64) / (pi_den as f64);
254 let sin: f64 = angle.sin();
255 let cos: f64 = angle.cos();
256 if is_significant(re / cos - im / sin) {
257 continue;
258 }
259 // We recognized the angle. Now try to recognize magnitude.
260 // It's OK to take abs value as we are only interested in magnitude
261 if let Some(magnitude) = RationalNumber::recognize((re / cos).abs()) {
262 return Some(Self::new(
263 &magnitude,
264 if im >= 0.0 { pi_num } else { pi_num - pi_den },
265 pi_den,
266 ));
267 }
268 }
269 None
270 }
271}
272
273/// Represents a non-zero complex number in the Cartesian form: ``real_part+𝒊·imaginary_part``
274/// Sign of the number is separated for easier composition and rendering
275#[derive(Debug)]
276struct CartesianForm {
277 sign: i64, // 1 the common sign is a "+", -1 is "-", 0 means the number is 0
278 real_part: RealNumber, // Real part
279 imaginary_part: RealNumber, // Imaginary part
280}
281
282impl CartesianForm {
283 fn new(real_part: RealNumber, imaginary_part: RealNumber) -> Self {
284 let sign = real_part.sign();
285 match sign {
286 0 => Self {
287 sign: imaginary_part.sign(),
288 real_part: RealNumber::Zero,
289 imaginary_part: imaginary_part.abs(),
290 },
291 1.. => Self {
292 sign,
293 real_part,
294 imaginary_part,
295 },
296 _ => Self {
297 sign,
298 real_part: real_part.abs(),
299 imaginary_part: imaginary_part.negate(),
300 },
301 }
302 }
303
304 /// Try to recognize a complex number and represent it in the Cartesian form.
305 fn recognize(re: f64, im: f64) -> Self {
306 Self::new(RealNumber::recognize(re), RealNumber::recognize(im))
307 }
308}
309
310/// Represents a non-zero complex number which can be in either polar or Cartesian form.
311#[derive(Debug)]
312enum ComplexNumber {
313 Polar(PolarForm),
314 Cartesian(CartesianForm),
315}
316
317impl ComplexNumber {
318 fn recognize(re: f64, im: f64) -> Self {
319 if let Some(exponent) = PolarForm::recognize(re, im) {
320 Self::Polar(exponent)
321 } else {
322 Self::Cartesian(CartesianForm::recognize(re, im))
323 }
324 }
325}
326
327/// Represents one term of a quantum state, which corresponds to one basis vector.
328struct Term {
329 basis_vector: BigUint,
330 coordinate: ComplexNumber,
331}
332
333fn get_terms_for_state(state: &Vec<(BigUint, Complex64)>) -> Vec<Term> {
334 let mut result: Vec<Term> = Vec::with_capacity(state.len());
335 for (basis_vector, coefficient) in state {
336 result.push(Term {
337 basis_vector: basis_vector.clone(),
338 coordinate: ComplexNumber::recognize(coefficient.re, coefficient.im),
339 });
340 }
341 result
342}
343
344/// Get the state represented as a formula in the LaTeX format if possible.
345/// Empty string is returned if the resulting formula is not nice, i.e.
346/// if the formula consists of more than 16 terms or if more than two coefficients are not recognized.
347#[must_use]
348pub fn get_latex(state: &Vec<(BigUint, Complex64)>, qubit_count: usize) -> String {
349 if state.len() > 16 {
350 return String::new();
351 }
352
353 let terms: Vec<Term> = get_terms_for_state(state);
354 let mut bad_term_count: i64 = 0;
355 for term in &terms {
356 if let ComplexNumber::Cartesian(cartesian) = &term.coordinate {
357 if let RealNumber::Decimal(_) = &cartesian.real_part {
358 bad_term_count += 1;
359 }
360 if let RealNumber::Decimal(_) = &cartesian.imaginary_part {
361 bad_term_count += 1;
362 };
363 if bad_term_count > 2 {
364 return String::new();
365 }
366 }
367 }
368
369 let mut latex: String = String::with_capacity(200);
370 latex.push_str("$|\\psi\\rangle = ");
371 let mut is_first: bool = true;
372 for term in terms {
373 write_latex_for_term(&mut latex, &term, !is_first);
374 let basis_label = fmt_basis_state_label(&term.basis_vector, qubit_count);
375 write!(latex, "|{basis_label}\\rangle").expect("Expected to write basis label.");
376 is_first = false;
377 }
378 latex.push('$');
379 latex.shrink_to_fit();
380
381 latex
382}
383
384/// Write latex for one term of quantum state.
385/// Latex is rendered for coefficient only (not for basis vector).
386/// + is rendered only if ``render_plus`` is true.
387fn write_latex_for_term(latex: &mut String, term: &Term, render_plus: bool) {
388 match &term.coordinate {
389 ComplexNumber::Cartesian(cartesian_form) => {
390 write_latex_for_cartesian_form(latex, cartesian_form, render_plus);
391 }
392 ComplexNumber::Polar(polar_form) => {
393 write_latex_for_polar_form(latex, polar_form, render_plus);
394 }
395 }
396}
397
398/// Write latex for polar form of a complex number.
399/// The sign is always + and is rendered only if ``render_plus`` is true.
400fn write_latex_for_polar_form(latex: &mut String, polar_form: &PolarForm, render_plus: bool) {
401 if polar_form.sign < 0 {
402 latex.push('-');
403 } else if render_plus {
404 latex.push('+');
405 }
406 write_latex_for_algebraic_number(latex, &polar_form.magnitude, false);
407 latex.push_str(" e^{");
408 if polar_form.phase_multiplier.sign < 0 {
409 latex.push('-');
410 }
411 let pi_num: i64 = polar_form.phase_multiplier.numerator;
412 if pi_num != 1 {
413 write!(latex, "{pi_num}").expect("Expected to write phase numerator.");
414 }
415 latex.push_str(" i \\pi");
416 let pi_den = polar_form.phase_multiplier.denominator;
417 if pi_den != 1 {
418 write!(latex, " / {pi_den}").expect("expected to write phase denominator.");
419 }
420 latex.push('}');
421}
422
423/// Write latex for cartesian form of a complex number.
424/// Common + is rendered only if ``render_plus`` is true.
425/// Brackets are used if both real and imaginary parts are present.
426/// If only one part is present, its sign is used as common.
427/// If both components are present, real part sign is used as common.
428/// 1 is not rendered, but + is rendered if ``render_plus`` is true.
429fn write_latex_for_cartesian_form(
430 latex: &mut String,
431 cartesian_form: &CartesianForm,
432 render_plus: bool,
433) {
434 if cartesian_form.sign < 0 {
435 latex.push('-');
436 } else if render_plus {
437 latex.push('+');
438 }
439 if let RealNumber::Zero = cartesian_form.real_part {
440 if let RealNumber::Zero = cartesian_form.imaginary_part {
441 // NOTE: This branch is never used.
442 latex.push('0');
443 } else {
444 // Only imaginary part present
445 write_latex_for_real_number(latex, &cartesian_form.imaginary_part, false);
446 latex.push('i');
447 }
448 } else if let RealNumber::Zero = cartesian_form.imaginary_part {
449 // Only real part present
450 write_latex_for_real_number(latex, &cartesian_form.real_part, false);
451 } else {
452 // Both real and imaginary parts present
453 latex.push_str("\\left( ");
454 write_latex_for_real_number(latex, &cartesian_form.real_part, true);
455 latex.push(if cartesian_form.imaginary_part.sign() < 0 {
456 '-'
457 } else {
458 '+'
459 });
460 write_latex_for_real_number(latex, &cartesian_form.imaginary_part, false);
461 latex.push_str("i \\right)");
462 }
463}
464
465/// Write latex for real number. Note that the sign is not rendered.
466/// 1 is only rendered if ``render_one`` is true. 0 is rendered, but not used in current code.
467fn write_latex_for_real_number(latex: &mut String, number: &RealNumber, render_one: bool) {
468 match number {
469 RealNumber::Algebraic(algebraic_number) => {
470 write_latex_for_algebraic_number(latex, algebraic_number, render_one);
471 }
472 RealNumber::Decimal(decimal_number) => {
473 write_latex_for_decimal_number(latex, decimal_number, render_one);
474 }
475 RealNumber::Zero => {
476 // Note: this arm is not used.
477 latex.push('0');
478 }
479 }
480}
481
482/// Write latex for decimal number. Note that the sign is not rendered.
483/// 1 is only rendered if ``render_one`` is true.
484fn write_latex_for_decimal_number(latex: &mut String, number: &DecimalNumber, render_one: bool) {
485 if render_one || is_significant(number.value - 1.0) {
486 // Using round() instead of neater string formatting({:.4})
487 // because we do not want trailing zeros (we need 0.5 and not 0.5000)
488 write!(latex, "{}", (number.value * 10000.0).round() / 10000.0)
489 .expect("Expected to write decimal value.");
490 }
491}
492
493/// Write latex for algebraic number. Note that the sign is not rendered.
494/// 1 is only rendered if ``render_one`` is true.
495fn write_latex_for_algebraic_number(
496 latex: &mut String,
497 number: &AlgebraicNumber,
498 render_one: bool,
499) {
500 let actually_needs_1: bool = render_one || number.fraction.denominator != 1;
501 if number.fraction.denominator != 1 {
502 latex.push_str("\\frac{");
503 }
504 if number.root == 1 {
505 if number.fraction.numerator == 1 {
506 if actually_needs_1 {
507 latex.push('1');
508 }
509 } else {
510 write!(latex, "{}", number.fraction.numerator).expect("Expected to write numerator.");
511 }
512 } else if number.fraction.numerator == 1 {
513 write!(latex, "\\sqrt{{{}}}", number.root)
514 .expect("Expected to write square root expression.");
515 } else {
516 write!(
517 latex,
518 "{} \\sqrt{{{}}}",
519 number.fraction.numerator, number.root
520 )
521 .expect("expected to write numerator and square root expression.");
522 }
523 if number.fraction.denominator != 1 {
524 write!(latex, "}}{{{}}}", number.fraction.denominator)
525 .expect("Expected to write denominator.");
526 }
527}
528