https://t.co/p9mHLI3Llm
Talk abstract: Quantum computers will pose a major threat to the cryptography we use today. But quantum physics also lets us do things that are impossible classically. With quantum key distribution, for example, two people can share a secret key without a computational hardness assumption. We can even have digital tokens that can’t be copied, such as quantum money and one-shot signatures.
In this talk I’ll highlight two examples of “quantum-powered cryptography” and speculate about what they might have to do with AI safety and alignment. First, there’s a whole world of quantum cryptographic primitives that rely on fewer mathematical assumptions than we need classically. Given the recent spate of AI cryptanalysis results, there's urgency in finding cryptosystems that rely on as few assumptions as possible.
Second, I will talk about interactive proofs of physical location. Trustworthy proofs of location are not possible in a classical world, but are possible in a quantum world via *quantum position verification* protocols. I will discuss how such protocols may be helpful for problems in AI alignment (e.g., holding AI agents liable for their actions).
This Monday I'm giving a talk at the Institute for Advanced Study on "Quantum Cryptography for the AI age". I'll talk about how contemporary concerns about AI collide with recent advancements in quantum cryptography. If you're in the Princeton area and want to chat, let me know!
If you value quality over quantity, consider signing the TCS hiring statement. Bean counting is obsolete. No point in pushing students to produce more and more AI-generated papers.
https://t.co/gBpUTLIOfl
In 1966, Paul Cohen won the Fields medal for showing the independence of: the continuum hypothesis and the axiom of choice.
Gödel reacted to Cohen’s Fields medal by saying that he had already proved the result in the 1940s. Yet when pushed for a proof by his peers, Gödel was unable to reconstruct one from his notes.
"The first task von Plato set Claude was to discover if Gödel’s workbooks had a proof of the independence of the axiom of choice, which would reveal that Gödel had been telling the truth in 1966.
The answer came back: yes, almost. “He was just one step away,”"
Ruben and I are thankful for the support of Microsoft Quantum to do fundamental research on the capabilities of measurement-based quantum computing. In particular, we really want to understand how intermediate classical processing can help (or not) with steering a quantum computation. Ruben and I come from very different backgrounds -- he's a condensed matter theorist, and I'm a computer scientist -- but we've realized that we care a lot about the same questions. An example of a question we are really interested in is how the computational power of the classical processor can affect what kinds of quantum states can be prepared by shallow, dynamic quantum circuits.
"Columbia Computer Scientist Henry Yuen Is Looking to Make the Most of Microsoft’s Quantum Hardware
Yuen and University of Chicago's Ruben Verresen have received $100,000 from the company’s Quantum Pioneers Program."
https://t.co/Sd0W6MAtWt
@ColumbiaQuantum@EE_ColumbiaSEAS
I've been skeptical of various efforts involving the publicly-made STOC 2027 submissions, but this is cool. Trying to contribute to it wrt my own submission.
🚀 STOC 2027, a flagship conference in theoretical computer science, made all 1,665 submissions publicly available. So we launched the STOC 2027 Formalization Initiative on Prove2Me!
Our AI agents have translated the main theorems and supporting lemmas of 1,496 submissions into Lean 4 statements!
Some already have completed proof formalizations, with many more awaiting contributions.
You don't need to know Lean or fully understand the underlying mathematics to get started! If you know how to work with AI agents, you can help formalize proofs.
We invite authors, researchers, and the broader community to explore these formalized statements, check them against the original papers, and contribute proof formalizations!
📊 Explore the initiative: https://t.co/KJWtxfRKLB
🤝 Contribute proof formalizations: https://t.co/aQ1NKnO1c0
You can test whether n is prime deterministically and in polynomial time in 10 lines of Python. This algorithm is Gary Miller's from 50 years ago. But the proof requires OpenAI's recent quasi-GRH result!
The AKS primality test was a huge deal (Gödel and Fulkerson prizes in 2006) but now it's obsolete. Crazy times.
I guess our priors have shifted, but at least in terms of relative confidence, I think most would still bet that SHA256 is more likely to be quantum-secure than LWE.
This is too strong of an interpretation, for a couple reasons. First, Aaronson-Ambainis compares quantum vs classical algorithms when they have access to an idealized, perfectly unstructured black box oracle. All cryptographic hash functions are not black box and definitely not unstructured (because their source code is succinct and public). We should be very wary about transferring conclusions about random oracles to concrete hash functions.
Second, Aaronson-Ambainis is about decision problems concerning the black box oracle. We now know there is no exponential quantum advantage for decision problems on unstructured oracles. On the other hand, search problems are a completely different story. We know there can be exponential quantum advantage for solving search problems related to unstructured oracles; this is the famous Yamakawa-Zhandry result from 2022.
This second item is particularly relevant to breaking hash functions, where you want to do things like "Find me a preimage -- any preimage -- of this hash value".
I think this result strongly suggests that quantum computers do *not* have an exponential advantage when attempting to break secure hash functions. Gg, CRQCs.
For Aaronson-Ambainis, you have to remember that in quantum computing we say "query complexity" the way that biologists say "in mice."
As in "we can cure cancer in mice" or "we know the power of QCs in query complexity."
Excited to see that the Aaronson-Ambainis conjecture has apparently been proved! But depressed to see the amount of completely incorrect commentary on its implications, so here's an attempt to clear things up.