This market resolves YES if someone publishes a working quantum circuit implementation that successfully factors 77 into 7 and 11 using IBM's cloud quantum computing service before March 1st, 2025. The implementation must be publicly available (e.g. on GitHub, arXiv, or similar platform) and verifiably demonstrate successful factorization on IBM's platform. Resolution will be based on public announcements, academic publications, or verifiable GitHub repositories showing working code.
Motivated by Martin Shkreli's tweet:
1,000
3.00I ended up trying this guy's solution, and it does seem to reliably return the prime factors of odd semi-primes (including 77). It doesn't appear to be very good at factoring even semi-primes, it just finds 2.
This is more along the lines of what i expected
@QuantumObserver I don’t see how it’s legitimate to compute the GCD of every number with 77 classically. If you can use that, finding a prime factor is trivial (the first integer n ≥ 2 with GCD(n, 77) ≠ 1 is a prime factor).
@QuantumObserver yeah, it seems like a lot of classical precomputation is going on that makes this not really a quantum computation. At least in the semiprime case knowing the GCD of everything with the number you want to factor makes it trivial (since only multiples of 7 and 11 will have GCD > 1).
In the code that you ended up running, 43 was picked by a human because 43-1 is a multiple of 7 and 43+1 is a multiple of 11. The essential computation does not occur in this program at all.
Maybe I misunderstood what you were asking, but Wikipedia, Stack Exchange, and other sources give the largest number previously factored by quantum computer (via Shor, not counting annealing methods) as 21, and even that used foreknowledge of the factorization. I am skeptical that this represents a genuine quantum computation that is such a large advancement over the state of the art.
@derikk I think you have both a good point and are slightly confused.
1. Everything step to the modular exponentiation calculation is expected to occur classically for Shor's algorithm. Calculating the gcd() is required to ensure we don't find a non-trivial case. I actually use the `arbitraryNShor.py` script in the GitHub repo linked in the tweet (here: https://github.com/Curtisflo/QuantumFactorization). The code explicitly does not keep values of `gcd(a, N) == 1` and instead continues on to use trivial factors.
2. This script does try to find initial guesses a that satisfy `gcd(a, N) == 1` so that the number of quantum steps are fewer, but it is wrong to say that the 'essential computation' does not occur. I have tried the same script with relaxed conditions on a and while the results are not as good (usually you only find one of the two primes), it is still able to do some factoring. And, critically, the modular exponentiation and inverse quantum Fourier transform are completed using quantum gates on a quantum computer. We can argue about the brittleness of this result (it fails on even semiprimes). It's worth noting that I tried factoring a small composite prime (105) with this approach and it did find a factor (15). So, imo, the algorithm does what it says (factoring). I think I could do it better or perhaps more interestingly worse, but that's a matter for a different market.
3. The published factorizations that I've seen were all constrained to low-qubit count IBM machines and specifically focused on performing these calculations with as few qubits as possible. Right now, by default, I am able to access 3x 127 qubit machines for free, so this constraint has been substantially relaxed. I don't think skepticism from the perspective of previous work is warranted. I agree that using foreknowledge of the outcome is not desirable so you'd want to write an implementation that's as agnostic to this knowledge as possible, without having to go factor a 2048 bit prime to be sure. I'm interested in such an approach as well.
Afaict BLUECOW009 found the trivial solution that doesn’t actually require any quantum operations (gcd != 1), which violates the spirit of this market. I will edit to make more clear, happy to refund your bet if you want.
I’m willing to be proved wrong here, if/when BLUECOW009 posts the code.
Seems very unlikely: https://manifold.markets/xyz/will-a-quantum-computer-factor-a-6b
@derikk the paper that post is referring to can be found here:
https://arxiv.org/pdf/1903.00768
AFAICT, most published factoring attempts thus far have been restricted to the 5 qubit QPUs, but I'm still performing my literature search to make sure. My IBMQ dashboard shows access to several 127 qubit machines, right now, so I am actually pretty optimistic that this can be done, if it hasn't been already.