Simon's algorithm example

[oxarbitrage]

Had been experimenting with the Simon's algorithm and i was able to write some code for the simulator. It has a lot of room for improvements, most notorious from my point of view:

• BitVec was introduced as a dependency but there are still some conversions between string types and loops that could be improved.
• I was not able to code the final system of equations solver, i added a TODO comment in the code, will be great to have it.

Program output:

2-bit secrets:

Secret string is 0b00 as this is uniformly distributed with prob 1/(2.exp(n))
Secret string is 0b11 as the likelhood is 1/2.exp(n-1)
Secret string is 0b10 as the likelhood is 1/2.exp(n-1)
Secret string is 0b01 as the likelhood is 1/2.exp(n-1)

3-bit secrets:

Secret string is 0b000 as this is uniformly distributed with prob 1/(2.exp(n))

Secret: 0b001, Measured: 0b100 - Confirmation: 0b001.0b100 = 0 (mod 2)
Secret: 0b001, Measured: 0b010 - Confirmation: 0b001.0b010 = 0 (mod 2)
Secret: 0b001, Measured: 0b110 - Confirmation: 0b001.0b110 = 0 (mod 2)

Secret: 0b010, Measured: 0b001 - Confirmation: 0b010.0b001 = 0 (mod 2)
Secret: 0b010, Measured: 0b100 - Confirmation: 0b010.0b100 = 0 (mod 2)
Secret: 0b010, Measured: 0b101 - Confirmation: 0b010.0b101 = 0 (mod 2)

Secret: 0b011, Measured: 0b111 - Confirmation: 0b011.0b111 = 0 (mod 2)
Secret: 0b011, Measured: 0b100 - Confirmation: 0b011.0b100 = 0 (mod 2)
Secret: 0b011, Measured: 0b011 - Confirmation: 0b011.0b011 = 0 (mod 2)

Secret: 0b100, Measured: 0b010 - Confirmation: 0b100.0b010 = 0 (mod 2)
Secret: 0b100, Measured: 0b001 - Confirmation: 0b100.0b001 = 0 (mod 2)
Secret: 0b100, Measured: 0b011 - Confirmation: 0b100.0b011 = 0 (mod 2)

Secret: 0b101, Measured: 0b010 - Confirmation: 0b101.0b010 = 0 (mod 2)
Secret: 0b101, Measured: 0b101 - Confirmation: 0b101.0b101 = 0 (mod 2)
Secret: 0b101, Measured: 0b111 - Confirmation: 0b101.0b111 = 0 (mod 2)

Secret: 0b110, Measured: 0b111 - Confirmation: 0b110.0b111 = 0 (mod 2)
Secret: 0b110, Measured: 0b110 - Confirmation: 0b110.0b110 = 0 (mod 2)
Secret: 0b110, Measured: 0b001 - Confirmation: 0b110.0b001 = 0 (mod 2)

Secret: 0b111, Measured: 0b101 - Confirmation: 0b111.0b101 = 0 (mod 2)
Secret: 0b111, Measured: 0b110 - Confirmation: 0b111.0b110 = 0 (mod 2)
Secret: 0b111, Measured: 0b011 - Confirmation: 0b111.0b011 = 0 (mod 2)

[Renmusxd]

Excellent! I'll go over this and eventually merge it in. I may try to either address the issues you mentioned or mitigate them (making bitvec a dev-dependency so it's not included in normal complications, for example)

[oxarbitrage]

Thanks.

I moved the bit-vec to be a dev dependency in https://github.com/Renmusxd/RustQIP/pull/34/commits/971e3c5c38aebfdc502bddbe93d3cd5fb3f7c189 . That was easier than what i thought.

Feel free to send commits into this PR. We can also merge and create tickets for future work if we don't have time to improve now.

[Renmusxd]

Sorry for the delay, it's actually owing mostly to a QIP class I'm taking. So right now I'm going to wait until we have the system of equations section set up. Hidden subgroup problems are such a key selling point for quantum computing that I want to make sure we have a clean example to showcase. If you don't know time to write out the last bit I can poke at it once I have some more time again.

[Renmusxd]

Merged into rewrite branch: https://github.com/Renmusxd/RustQIP/tree/oxisimons