- Hooray, I’m today’s “Featured ACM Member”! Which basically means, yet another interview with me about quantum computing, with questions including what’s most surprised me about the development of QC, and what students should do to get into the field.
- I’m proud to announce that An Automated Approach to the Collatz Conjecture, a paper by Emre Yolcu, myself, and Marijn Heule that we started working on over four years ago, is finally available on the arXiv, and will be presented at the 2021 Conference on Automated Deduction. Long story short: no, we didn’t prove Collatz, but we have an approach that can for the first time prove certain Collatz-like statements in a fully automated way, so hopefully that’s interesting! There was also a Quanta article even before our paper had come out (I wasn’t thrilled about the timing).
- The legendary Baba Brinkman has a new rap about quantum computing (hat tip to blog commenter YD). Having just watched the music video, I see it as one of the better popularization efforts our field has seen in the past 25 years—more coherent than the average journalistic account and with a much better backbeat. (I do, however, take a more guarded view than Brinkman of the potential applications, especially to e.g. autonomous driving and supply-chain optimization.)
This entry was posted
on Tuesday, June 1st, 2021 at 3:00 pm and is filed under Announcements, Quantum.
You can follow any responses to this entry through the RSS 2.0 feed.
Responses are currently closed, but you can trackback from your own site.
Follow
Comment #1 June 1st, 2021 at 3:34 pm
Hey Scott, some thoughts on the Collatz conjecture, some of which you undoubtedly know but I’d like this to be self-contained so bear with me:
In Collatz whenever you do a 3x+1 there’s always a division by two immediately afterwards, so a possibly cleaner formulation is to say that the steps are either (3x+1)/2 or x/2. This is sort of like flipping a coin as to whether you win or lose x/2 from your amount.
If you list the first k up/down events for the numbers from 1 to 2^k each possible one will occur exactly once. This is the ‘nice’ property which makes Collatz so intractable because you can’t pin it down to any particular behavior, everything always happens somewhere. If you take the mean of the kth step of all the numbers from 1 to 2^k it will generally be slightly more than 2^(k-1) because of the 1/2 added at each step, even though the median and geometric mean will be much lower because of the uneven distribution.
As it happens the alternating 1 2 terminal sequence of everything has equal numbers of up and down steps, but that isn’t true of every number you could possibly add. For example 3x+43 settles into a loop which has more down than up steps and 3x+53 has more up than down steps. Since smaller numbers get into the final loop faster than bigger numbers, the exactly even distributions mentioned earlier mean that the counterparts of those steps have to go larger numbers, which would seem to imply that the mean of the kth step of all the numbers from 1 to 2^k of 3x+43 is on average quite a bit more than 2^(k-1).
So… maybe the Collatz analogue 3x+43 isn’t true? And maybe 3x+53 is easier to prove?
Comment #2 June 1st, 2021 at 9:02 pm
Here are a few things that bothered me about that song:
* The figures with a bunch of Blach spheres side by side. I understand that it’s probably hard to put a \(2^53\)-dimensional Hilbert space in a video, but that picture makes it look like a boring classical analog computer.
* Applications like ML.
* He misproununced Mir. Mir doesn’t rhyme with “whir”. It (nearly) rhymes with “near”, “here”, and “sphere” that are literally right there in the same sentence.
Comment #3 June 1st, 2021 at 9:23 pm
A question inspired by the ACM interview: what would it take to factor a 1000-digit number with Shor’s algorithm? A huge number of qubits, much less noise, or both? Could we factor any number at all with 50-100 noisy qubits?
Comment #4 June 1st, 2021 at 9:37 pm
Tristram #3: The short answer is a few million qubits, and/or much better gate fidelities, and/or better error-correcting codes that can cope with near-future gate fidelities with much lower overhead.
With 50-100 noisy qubits, you can’t factor (or even fit) any number that’s not easily factored classically. People sometimes publish papers using adiabatic quantum computing to factor 5- or 6-digit numbers, but that’s just for the rubes — it doesn’t scale, doesn’t nontrivially involve quantum mechanics, and doesn’t demonstrate anything interesting.
Comment #5 June 1st, 2021 at 9:49 pm
> There was also a Quanta article even before our paper had come out (I wasn’t thrilled about the timing)
Do you think that if you requested them to wait for your paper to come out before publishing their article they would have respected your wish?
Comment #6 June 1st, 2021 at 10:22 pm
YD #2
Just some help with formatting, use the <sup> tag for superscripts
so “2<sup>53” for 253
or if you really want it bold
“<b>2<sup>53<\b>” for 253
Comment #7 June 2nd, 2021 at 1:12 am
First song I ever heard with “double exponential” in it!
Comment #8 June 2nd, 2021 at 6:37 am
In my amateur study of the collatz conjecture, it seems to need some insight into the prime factors of connective numbers.
Given n=p1*p2*p3…, what are the prime factors of n+1? (Or n-1)
Proving collatz may not require generally answering that question, but surely it would say something about it to prove termination.
I don’t see what the connection is between string rewriting and prime factors.
Am I missing something, or just wrong in thinking collatz boils down to understanding the prime factors of n+1?
Comment #9 June 2nd, 2021 at 6:50 am
Mo Nastri #5:
Do you think that if you requested them to wait for your paper to come out before publishing their article they would have respected your wish?
What happened was, I talked about our work-in-progress on Collatz because I was under the impression that it was going to form just one small part of a much broader article about automated theorem proving (which might indeed have been the original plan). I wasn’t prepared for Quanta to run a whole feature on a paper that didn’t exist yet—-I learned that it would only when that feature appeared. Yes, I think they would’ve respected my wishes if I’d known enough to explicitly formulate them. Lesson learned for next time!
Comment #10 June 2nd, 2021 at 9:24 am
Great stuff! Looking forward to read.
I think the following two references might be relevant:
Doron Zeilberger,
Teaching the Computer how to Discover(!) and then Prove(!!) (all by Itself(!!!)) Analogs of Collatz’s Notorious 3x+1 Conjecture,
https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/collatz.html
Błażewicz, Jacek; Pettorossi, Alberto
Some properties of binary sequences useful for proving Collatz’s conjecture.
https://zbmath.org/0547.10006
Comment #11 June 2nd, 2021 at 11:24 am
James Gallagher #6: You appear to have forgotten a number of semicolons…
Comment #12 June 2nd, 2021 at 12:46 pm
James Gallagher #6 Does escaping the open/close brackets work for all HTML tags, or just a whitelisted set?
The “sup” example: 2<sup>53</sup>
Something that really shouldn’t work: <script>alert(1)</script>
Comment #13 June 2nd, 2021 at 12:50 pm
Mike Stay #12 Oh, I see: the site messes up your HTML in order to sanitize it. 253 works.
Comment #14 June 2nd, 2021 at 4:23 pm
Mike #13, James #6
The preview plugin isn’t completely in sync with the WordPress sanitizing logic, but in this case it didn’t matter.
The issue with VD #2 is they used TeX with the code
2^53, which according to (La)TeX rules is \( 2^{5}3 \), regardless of this blog. The proper way is to use curly braces, i.e.2^{53}which should render as \( 2^{53} \).Comment #15 June 2nd, 2021 at 5:59 pm
Yes, I missed a pair of curly braces. Can we please not derail the comment section because of this? We can talk about quantum rap or Collatz conjecture or something.
—
I’m confused about example in section 4.2 and the claim that “Termination of the rewriting system \(\mathcal{F}\) is equivalent to the convergence of \(F\)”. The paper claims that the proof is the same as the proof of Theorem 3.15. But claim 3 of theorem 3.15 does not hold for Farkas’ function and the corresponding rewriting system: there are no rules applicable to \(\mathtt{⊲ff⊳}\), even though \(\mathrm{Val}(\mathtt{⊲ff⊳})=4\ne 1\). In fact, if the two least significant digits are in binary, none of the “interesting” rules \(\mathcal{D}_F\) can ever be used.
You could probably fix this by using binary-seximal mixed base instead of binary-ternary.
Comment #16 June 2nd, 2021 at 7:31 pm
I seem to have messed up that html formatting example, lol (it came out ok in the preview)
as Sniffnoy #11 suggested I needed some semicolons (which won’t display below)
2<sup>53</sup> displays as 253
<b>2<sup>53</sup></b> displays as 253
Mike #12
Not sure
(@ Scott, if this post displays as garbage when submitted just delete it, sorry!)
Comment #17 June 2nd, 2021 at 7:32 pm
yup, came out as garbage I give up, lol!
Comment #18 June 2nd, 2021 at 8:21 pm
YD #15:
That is a good point. The equivalence does hold, although I see now that calling the two proofs *essentially* the same was probably overkill. Claim 3 in the proof of Theorem 3.15 is stronger than necessary for the result it helps us achieve: from a nonconvergent trajectory we construct a nonterminating rewrite sequence. The actual argument for Farkas’ map is roughly the same for the forward direction (from rewrite sequences to trajectories). For the backward direction, take any nonconvergent F-trajectory, and write the first number in the trajectory in ternary. Then if we always perform the rightmost possible rewrite, the resulting rewrite sequence simulates the trajectory since it avoids running into a string that ends with two binary symbols. I hope that makes it clear, otherwise feel free to email me.
Comment #19 June 2nd, 2021 at 8:26 pm
Correction to Emre Yolcu #18: swap “forward” with “backward”.
Comment #20 June 2nd, 2021 at 8:56 pm
Filip Dimitrovski #14
Sorry I missed your comment, it explained the issue.
Comment #21 June 2nd, 2021 at 10:40 pm
Emre Yolcu #15: I see. That makes sense.
Do you think the fact that the rewrite system can “get stuck” like that makes finding a termination proof easier/harder? Or does it not matter?
Comment #22 June 3rd, 2021 at 3:59 am
Can we use this comment section to quible about notational issues in the paper? If not I’ll withdraw the comment. I really like the Colatz paper but I find the notation of Definition 3.9 very confusing because it is not clear what letters can be replaced by numbers in what way.
After studying the examples I think the source of the confusion is that the double index $${n_i}_{b_i}$$ was intended as $$(n_i)_{(b_i)}$$ while I interpreted initially as $$n_{(i_{(b_i)})}$$ which of course is also only one of many possibilities.
Nicely enough the latex-environment of this blog complains that I should clarify the braces before it will render my expressions, but may I recommend you do something similar in the paper? Human paper readers and automatic wordpress-latex-functions on blogs are not all that different in this respect.
Comment #23 June 3rd, 2021 at 4:16 am
OK, maybe I should withdraw my comment anyway since this notation issue is of course tiny compared to the overall interestingness of the paper.
Comment #24 June 3rd, 2021 at 12:12 pm
YD #21: Termination is a worst-case statement, so I don’t think it makes any difference. That said, the difficulty of finding an interpretation for some specific instance depends on several factors some of which we only know how to investigate empirically, so it’s hard to say something.
Comment #25 June 5th, 2021 at 11:38 pm
Would love to know more about your view on “quantum states as proofs or advice or unclonable currency”. I am very interested in that too.
Non-fungible tokens (cryptocurrency that is unique, like signed collectibles) is now all the rage in crytocurrency community. Could there be unique quantum states, such as an unknown quantum state prepared by an encrypted process/algorithm?
Comment #26 June 8th, 2021 at 2:04 pm
Daniel Tung #25: This is a big subject, but see e.g. my papers (especially, my two main quantum money papers here and here), or my Barbados lecture notes.
Comment #27 June 8th, 2021 at 2:40 pm
Check out Scott on Quanta:
https://www.quantamagazine.org/why-is-quantum-computing-so-hard-to-explain-20210608/
Comment #28 June 9th, 2021 at 1:27 pm
I read your Collatz paper, it was very interesting. In section 4.4 you discuss the related Syracuse function, and explicitly call out finding other functions with improved derivational complexity. I have some ideas in that direction.
Consider $$\text{Syr}'(n) = \frac{n}{2^{\lceil k/2 \rceil}}, n \text{ even; } 3n+1, n \text{ odd}$$ with \(k\) defined to be the maximal power of 2 dividing \(n\). I believe we can create a rewriting system implementing Syr’. The standard Collatz function takes $k$ steps to get from an odd number to an odd number; your function S takes (I believe) \(\lfloor\frac{k+1}{2}\rfloor \) steps; Syr’ takes ~\(lg(k)\) steps. Likewise, your rewriting systems take \(k\) steps to commute a trinary digit through a string of \(k\) f’s, and this system would take \(O(lg(k))\).
Here is the idea behind the rewriting system. Retain your symbols \(\langle,\rangle, f,t,0,1,2\); add symbols [,],u,d,S,H,x,y. We write \(n\) again as before in mixed binary/trinary with f,t,0,1,2, surrounded by \(\langle,\rangle\). However, M sequential f’s will be represented as f[M-1], with M-1 written in binary using bits u,d.
So instead of “f”, we have “f[]”, and instead of “fffff” we have “f[udd]”. Add a rule \([d \rightarrow [\) to get rid of leading 0s.
Now we drop the rules \(f0 \rightarrow 0f\), \(f1 \rightarrow 0t\), \(f2 \rightarrow 1t\), \(f\rangle \rightarrow \rangle\).
We instead have $$]0 \rightarrow 0], u0 \rightarrow 0u, d0 \rightarrow 0d, f[0 \rightarrow 0f[,$$ $$u]1 \rightarrow uSH]0t, d]1 \rightarrow dSH]0t, f[]1 \rightarrow 0t,$$ $$u]2 \rightarrow uSH]1t, d]2 \rightarrow dSH]1t, f[]2 \rightarrow 1t,$$ $$uS \rightarrow dy, dS \rightarrow Su, [S \rightarrow [x, yu \rightarrow uy, yh \rightarrow e, xu \rightarrow x, f[xH] \rightarrow e,$$ $$u]\rangle \rightarrow ]\rangle, d]\rangle \rightarrow ]\rangle, f[]\rangle \rightarrow \rangle.$$
The characters x,y,S,H implement a binary decrement Turing machine; the presence of the H prevents multiple decrements from happening at once. The last set of rules implements the \(n\) even case of Syr’.
Now, this already represents a partial speedup. To get the full speedup we would want a binary *adder*, so some \(O(lg(M+N))\) sequence of rewrites could take “f[M]f[N]” to “f[M+N]”, and do so without having issues with substrings of the form “f[M]f[N]0”, “f[M]f[N]1”, “f[M]f[N]2”, “f[M]f[N]f[P]”.
Comment #29 June 9th, 2021 at 1:32 pm
Actually, we can do one better and drop the symbol f entirely, it is extraneous to the system above.
Comment #30 June 9th, 2021 at 1:35 pm
And of course we actually want to take “[M][N]” to “[M+N+1]” considering the definition above.
Comment #31 July 2nd, 2021 at 1:06 pm
In order to prove the Collatz Conjecture, there has to be a logical reason why the sequence cannot diverge to infinity. But there is nothing stopping the sequence from diverging to infinity (which can happen if the overwhelming majority of iterates involve the function (3n+1)/2 instead of n/2). Therefore there is no logical reason why the Collatz conjecture must be true. In fact it is not true when you take 3n-1 instead of 3n+1 – there are at least two cycles. And it appears to diverge when you take 5n+1 instead of 3n+1. The only reason why the conjecture appears to be true is because the odds of getting a number n with the overwhelming majority of iterates to be (3n+1)/2 is about zero.
Comment #32 July 2nd, 2021 at 4:51 pm
Craig #31: Indeed, there’s no obvious reason why the Collatz conjecture has to be true. You ignore the possibility of non-obvious reasons, the discovery of which is the entire point of mathematical research.
Comment #33 July 3rd, 2021 at 10:21 pm
There is a theorem that says that for every vector x of size k of zeroes and ones, there exists an integer n such that the Collatz iterates of n correspond to the vector x, i.e., when an iterate is n/2, the corresponding entry of x is zero and when an iterate is (3n+1)/2, the corresponding entry of x is one. This shows that no behavior of a Collatz sequence can be ruled out a priori. So there is no reason, obvious or non obvious, why a Collatz sequence cannot have an overwhelming number of iterates (3n+1)/2; as soon as you give me a reason why a Collatz sequence must eventually go to one, I can give you an example of an n where it continues to diverge for the same length of time. I am not sure what the point of mathematical research is besides it being interesting.
Comment #34 July 4th, 2021 at 10:46 am
Craig #33: Have you heard of Goodstein sequences? You can easily find examples where an absurdly long time is needed until convergence—longer than the age of the universe, if you were naively plugging it into a computer. And yet we know that it always will converge, because there’s a proof.
Over nearly 20 years (!) of such comments, your aggressive ignorance has proved itself about the most impenetrable of any I’ve ever seen. Thus, now that I’ve explained the matter for anyone else who might be reading, all further comments from you will remain in moderation.