Git Product home page Git Product logo

rustqip's Introduction

RustQIP

Quantum Computing library leveraging graph building to build efficient quantum circuit simulations.

qip on crates.io qip docs unsafe forbidden

See all the examples in the examples directory.

PRs welcome

Rust is a great language for quantum computing with gate models because the borrow checker is very similar to the No-cloning theorem.

See all the examples in the examples directory of the Github repository.

Example (CSWAP)

Here's an example of a small circuit where two groups of Registers are swapped conditioned on a third. This circuit is very small, only three operations plus a measurement, so the boilerplate can look quite large in comparison, but that setup provides the ability to construct circuits easily and safely when they do get larger.

use qip::prelude::*;
use std::num::NonZeroUsize;

// Make a new circuit builder.
let mut b = LocalBuilder::<f64>::default();
let n = NonZeroUsize::new(3).unwrap();

// Make three registers of sizes 1, 3, 3 (7 qubits total).
let q = b.qubit();  // Same as b.register(1)?;
let ra = b.register(n);
let rb = b.register(n);

// Define circuit
// First apply an H to q
let q = b.h(q);
// Then swap ra and rb, conditioned on q.
let mut cb = b.condition_with(q);
let (ra, rb) = cb.swap(ra, rb) ?;
let q = cb.dissolve();
// Finally apply H to q again.
let q = b.h(q);

// Add a measurement to the first qubit, save a reference so we can get the result later.
let (q, m_handle) = b.measure(q);

// Now q is the end result of the above circuit, and we can run the circuit by referencing it.

// Run circuit with a given precision.
let (_, measured) = b.calculate_state_with_init([( & ra, 0b000), ( & rb, 0b001)]);

// Lookup the result of the measurement we performed using the handle, and the probability
// of getting that measurement.
let (result, p) = measured.get_measurement(m_handle);

// Print the measured result
println!("Measured: {:?} (with chance {:?})", result, p);

The Program Macro

While the borrow checker included in rust is a wonderful tool for checking that our registers are behaving, it can be cumbersome. For that reason qip also includes a macro which provides an API similar to that which you would see in quantum computing textbooks. This is guarded behind the macros feature.

use qip::prelude::*;
use std::num::NonZeroUsize;
use qip_macros::program;

fn gamma<B>(b: &mut B, ra: B::Register, rb: B::Register) -> CircuitResult<(B::Register, B::Register)>
    where B: AdvancedCircuitBuilder<f64>
{
    let (ra, rb) = b.toffoli(ra, rb)?;
    let (rb, ra) = b.toffoli(rb, ra)?;
    Ok((ra, rb))
}

let n = NonZeroUsize::new(3).unwrap();
let mut b = LocalBuilder::default();
let ra = b.register(n);
let rb = b.register(n);

let (ra, rb) = program!(&mut b; ra, rb;
    // Applies gamma to |ra[0] ra[1]>|ra[2]>
    gamma ra[0..2], ra[2];
    // Applies gamma to |ra[0] rb[0]>|ra[2]>
    // Notice ra[0] and rb[0] are grouped by brackets.
    gamma [ra[0], rb[0]], ra[2];
    // Applies gamma to |ra[0]>|rb[0] ra[2]>
    gamma ra[0], [rb[0], ra[2]];
    // Applies gamma to |ra[0] ra[1]>|ra[2]> if rb == |111>
    control gamma rb, ra[0..2], ra[2];
    // Applies gamma to |ra[0] ra[1]>|ra[2]> if rb == |110> (rb[0] == |0>, rb[1] == 1, ...)
    control(0b110) gamma rb, ra[0..2], ra[2];
)?;

We can also apply this to functions which take other arguments. Here gamma takes a boolean argument skip which is passed in before the registers. The arguments to functions in the program macro may not reference the input registers

use qip::prelude::*;
use std::num::NonZeroUsize;
use qip_macros::program;

fn gamma<B>(b: &mut B, skip: bool, ra: B::Register, rb: B::Register) -> CircuitResult<(B::Register, B::Register)>
    where B: AdvancedCircuitBuilder<f64>
{
    let (ra, rb) = b.toffoli(ra, rb)?;
    let (rb, ra) = if skip {
        b.toffoli(rb, ra)?
    } else {
        (rb, ra)
    };
    Ok((ra, rb))
}
let n = NonZeroUsize::new(3).unwrap();
let mut b = LocalBuilder::default();
let ra = b.register(n);
let rb = b.register(n);

let (ra, rb) = program!(&mut b; ra, rb;
    gamma(true) ra[0..2], ra[2];
    gamma(0 == 1) ra[0..2], ra[2];
)?;

The Invert Macro

It's often useful to define functions of registers as well as their inverses, the #[invert] macro automates much of this process.

use qip::prelude::*;
use std::num::NonZeroUsize;
use qip_macros::*;
use qip::inverter::Invertable;

// Make gamma and its inverse: gamma_inv
#[invert(gamma_inv)]
fn gamma<B>(b: &mut B, ra: B::Register, rb: B::Register) -> CircuitResult<(B::Register, B::Register)>
    where B: AdvancedCircuitBuilder<f64> + Invertable<SimilarBuilder=B>
{
    let (ra, rb) = b.toffoli(ra, rb)?;
    let (rb, ra) = b.toffoli(rb, ra)?;
    Ok((ra, rb))
}

let n = NonZeroUsize::new(3).unwrap();
let mut b = LocalBuilder::default();
let ra = b.register(n);
let rb = b.register(n);

let (ra, rb) = program!(&mut b; ra, rb;
    gamma ra[0..2], ra[2];
    gamma_inv ra[0..2], ra[2];
)?;

To invert functions with additional arguments, we must list the non-register arguments.

use qip::prelude::*;
use std::num::NonZeroUsize;
use qip_macros::*;
use qip::inverter::Invertable;

// Make gamma and its inverse: gamma_inv
#[invert(gamma_inv, skip)]
fn gamma<B>(b: &mut B, skip: bool, ra: B::Register, rb: B::Register) -> CircuitResult<(B::Register, B::Register)>
    where B: AdvancedCircuitBuilder<f64> + Invertable<SimilarBuilder=B>
{
    let (ra, rb) = b.toffoli(ra, rb)?;
    let (rb, ra) = if skip {
        b.toffoli(rb, ra)?
    } else {
        (rb, ra)
    };
    Ok((ra, rb))
}

let n = NonZeroUsize::new(3).unwrap();
let mut b = LocalBuilder::default();
let ra = b.register(n);
let rb = b.register(n);

let (ra, rb) = program!(&mut b; ra, rb;
    gamma(true) ra[0..2], ra[2];
    gamma_inv(true) ra[0..2], ra[2];
)?;

rustqip's People

Contributors

atwupack avatar kvark avatar ommyzhang avatar oxarbitrage avatar renmusxd avatar rozkerim avatar sunsided avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

rustqip's Issues

Add circuit compilation + optimization

Circuits need to be able to be compiled to match the gatesets of specific hardware implementations - furthermore there should be the ability to optimize circuits to reduce gate counts (weighted by the difficulty for each).
In general this problem is intractable, but simulated annealing is reasonably good at it.

Clippy lints

Tried to run clippy in the repo and there are a lot of lints, we should try to fix it as it will allow developers to merge better code.

Will be nice if the following command passes without warnings or errors at some time in the future:

cargo clippy --all-features --all-targets

Make an SVG drawing backend.

There currently existing a console output backend which draws the circuit, but a configurable svg drawing option would be nice for including diagrams in papers or debugging circuits.

Improve documentation and add more inline doc examples.

All public structs and functions have docs, but docs can always be improved and examples are worth a thousand words. A comprehensive review to clean up documentation and provide detailed examples makes everyone's life easier.

Add support for statistical mixtures of quantum states.

Quantum circuits often have statistical mixtures of states (meaning there's a classical probability of having any of a set of quantum states). Implementing gates which provide classical noise and produce these mixtures can better match real life applications.

These mixtures would likely need to have a minimum probability or max number of states to prevent exponential blowup of memory usage with the number of applications of these noisy gates.

Add distributed computing backend.

This was implemented in the older python QIP project. See this directory:
https://github.com/Renmusxd/QIP/tree/master/qip/distributed

Since memory size grows exponentially you will often run out of ram before computation time becomes the bottleneck. Given rust recently added async support to the stable branch it is probably a good time to start thinking about distributed backends for RustQIP.
Initial thought is to have a implementation of the QuantumState trait which would send operations to a server, the server implementation isn't terribly restricted however, and can be written more or less from scratch.

Add some more basic quantum algorithms

There are many small functions which make appearances in a variety of larger algorithms, it would probably be worth implementing a sort of quantum standard library to improve coding quality of life and decrease debugging time.

Linear type and quantum logic

o/ I am currently figuring out how to do Birkhoff-von Neumann quantum logic operation in a quantum circuit, and found that the linear type (a subset of linear logic) has already been manifested in Rust, in particular in its borrow checker. I am looking for an advice / resource recommendation on:

  • which file I should look at in this repo to see the borrow checker being used to ensure the no-cloning property.
  • how you could solve systems that can be modeled in linear logic in RustQIP.
  • if you know a specific example of a large scale system that is solved with linear logic, given that the resource interpretation. implies that it could be used to model energy-based currency/trade between systems.
  • how to implement quantum logic in the language of quantum logic gates, essentially a reverse of [1], cc: @udallago

Another interpretation of linear logic, is to be considered as a 2-player game, as can be found in [2]

In A โŠ— B, play continues with both games in parallel. If it is our turn in either game, then it is our turn overall; if it is their turn in both games, then it is their turn overall. If either game ends, then play continues in the other game; if both games end, then the overall game ends. If we have won both games, then we have won overall; if they have won either game, then they have won overall.

[1] https://arxiv.org/abs/1210.0613
[2] https://ncatlab.org/nlab/show/linear+logic#game_semantics_2

Add circuit serialization.

Serializing a circuit and loading it later seems like a nice QoL feature. Special consideration needs to be made to the ops which rely on the value of a measurement (perhaps adding a serializable match statement op?).

Fix the endianess problem

The 0th qubit can either refer to the least significant or most significant position depending on the context. This makes it confusing to work on internals and should be resolved before the 1.0 release ( Issue #6 ).

Add more examples.

More examples in the directory, particularly showcasing common algorithms or fun results, can help people get used to writing circuits.

Faer rs Backend

Hi,

Are you aware of Faer-rs crate ? It has very strong performance, on par with openblas, intel-mkl, without dealing with c/c++ bindings.
It should provide great performance boost for appropriate fundamental operations, e.g. complex gemm (conjugate or not)
One can start with including it slowly as an optional backend for some ops.

Add QASM output

Add support for writing qasm files from the generated circuits.

Add more benchmarks

Current benchmarks focus on executing ops on a state, while this is the bulk of the computational load there are many other features that should be tested, such as program!, invert_fn!, and unitary decomposition.

Add Feynman path integral backend

The existing backend is "Schrodinger"-style, which means it stores the entire wavefunction, runtime is O(2^N M) and space is O(2^N) where N is the number of qubits and M the number of gates. A Feynman path integral backend would sum up all the possible paths from the input to the output through the circuit, making the runtime exponential in the circuit depth, but the memory footprint constant. This may be difficult to implement because of measurements taken midway through the circuit, but would be very helpful for certain circuit types. Furthermore there are likely mixed S-F algorithms which can optimize space/runtime tradeoffs.

Find minimum version numbers for dependencies.

While not strictly necessary, finding the minimum viable version numbers for the dependencies just seems less arbitrary than "whatever was most current when we added it". Not sure if there's an automated tool to do binary search across version numbers and run tests until it fails, but that's what we should do.

Rewrite for 1.0

Much of this library isn't idiomatic rust - nor is it really well written to be honest with myself.
The numerics under the hood are fine and fairly well optimized, the issue is that the UnitaryBuilder trait and pipeline constructor heavily uses dynamic dispatch. Switching over to generics and traits would allow for much more flexibility from a type system perspective.
This would require a large reorganization, and much of the responsibility of the classes would need to be moved around.

Document grovers algorithm example

Grovers algorithm code (https://github.com/Renmusxd/RustQIP/blob/master/examples/grovers.rs) has no comments in the code so understating how it works is not easy.

For example i can't understand why iterating 100 times with an N of 10 and how the correct key value x (42) is found from the printed outputs:

0	0.00877
1	0.02422
2	0.04711
3	0.07706
4	0.11362
5	0.15621
6	0.20416
7	0.25673
8	0.31310
9	0.37239
10	0.43367
11	0.49598
12	0.55836
13	0.61982
14	0.67942
15	0.73621
16	0.78932
17	0.83791
18	0.88123
19	0.91859
20	0.94943
21	0.97324
22	0.98967
23	0.99846
24	0.99946
25	0.99267
26	0.97819
27	0.95624
28	0.92717
29	0.89144
30	0.84959
31	0.80229
32	0.75026
33	0.69433
34	0.63537
35	0.57430
36	0.51206
37	0.44964
38	0.38800
39	0.32811
40	0.27091
41	0.21728
42	0.16806
43	0.12402
44	0.08586
45	0.05416
46	0.02941
47	0.01202
48	0.00224
49	0.00023
50	0.00602
51	0.01953
52	0.04053
53	0.06870
54	0.10361
55	0.14471
56	0.19135
57	0.24281
58	0.29828
59	0.35690
60	0.41776
61	0.47990
62	0.54235
63	0.60415
64	0.66431
65	0.72192
66	0.77605
67	0.82588
68	0.87063
69	0.90958
70	0.94215
71	0.96781
72	0.98617
73	0.99694
74	0.99995
75	0.99516
76	0.98264
77	0.96258
78	0.93531
79	0.90124
80	0.86091
81	0.81494
82	0.76406
83	0.70905
84	0.65078
85	0.59016
86	0.52813
87	0.46566
88	0.40373
89	0.34330
90	0.28532
91	0.23069
92	0.18026
93	0.13482
94	0.09508
95	0.06167
96	0.03509
97	0.01578
98	0.00402
99	0.00000

@Renmusxd if you can explain me briefly how it works in this issue i will be happy to send a PR to add comments details to the file.

Find and fix custom implementations of stdlib functions.

There are probably several places where custom implementations of algorithms are provided where stdlib versions exists. An example would be checking if a supplied u64 has only a single bit set, this could be done using is_power_of_two.

Debug QFFT

The quantum fft function was ported over from the python QIP project, but likely isn't entirely bug free (I was not able to write tests which I found satisfactory which also passed). This needs to be debugged and fixed, possibly also moved over to the common circuits directory.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.