Shor's algorithm works with very large integers; larger than 64 bits. So the built-in 64-bit Int type is insufficient for doing the classical processing (e.g. computing the multipliers $b^{2^k} \pmod{N}$). Is there a big int type suitable for those purposes?
$\begingroup$
$\endgroup$
2
asked Jan 1, 2019 at 2:11
-
1$\begingroup$ Are you okay with how to build it as a user defined type if there is not a built-in? $\endgroup$– AHusainJan 3, 2019 at 22:17
-
$\begingroup$ @AHusain Yes, that's a reasonable answer. $\endgroup$– Craig GidneyJan 4, 2019 at 2:20
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
There is none at the moment (as of version 0.3). We're working on adding it as a primitive type, hopefully it will be included in the next release.
answered Jan 4, 2019 at 1:40
-
1$\begingroup$ We released support for BigInt a week ago; see docs.microsoft.com/en-us/quantum/relnotes/?view=qsharp-preview. $\endgroup$ Feb 6, 2019 at 21:17
$\begingroup$
$\endgroup$
3
In the meantime you could make
newtype LongInt = (Int,Int)
where (a,b) could represent the integer $(2^{64}*a)+(b+2^{63})$
The arithmetic operations for this would then be overridden so you define your own (a,b)*(c,d) that gives another LongInt but with potential for overflow. So if this could be wrapped in Maybe monad, that would be better.
Continue this way like "long long int" that are 4 times the length of a standard 16 bit int in C.
You could make a different choice of how you want to encode larger integers as combinations of Int if you want.
-
$\begingroup$ That pushes the problem back to 128 bits, but I want numbers with tens of thousands of bits. I suppose I could use Int[] instead of (Int,Int)... Is there no way to bring in .net's existing bigint type? $\endgroup$ Jan 4, 2019 at 13:43
-
$\begingroup$ You could also double the bit length 9 more times and get into the 10000s. But I don't know if you really want arbitrarily large (memory nonwithstanding) or just 10000s bit large. $\endgroup$– AHusainJan 4, 2019 at 19:37
-
$\begingroup$ I think by the 4th doubling I'd be well into "I'm going to have to use a code generator" territory. The benefit of using an array is that the amount of code doesn't grow with the desired size. $\endgroup$ Jan 4, 2019 at 22:15
$\begingroup$
$\endgroup$
Q# now has a BigInt type included: https://docs.microsoft.com/en-us/quantum/user-guide/language/typesystem/#available-types
answered Dec 16, 2020 at 17:50