I have therefore reached a decision. From this day forward, my allegiances in the String Wars will be open for sale to the highest bidder. Like a cynical arms merchant, I will offer my computational-complexity and humor services to both sides, and publicly espouse the views of whichever side seems more interested in buying them at the moment. Fly me to an exotic enough location, put me up in a swank enough hotel, and the number of spacetime dimensions can be anything you want it to be: 4, 10, 11, or even 172.9+3πi.
i too, am a scott aaronson fan. his NP-completeness and physical reality is the snarkiest physics paper i have ever read. every now and then scott writes a paper that is a bit more widely accessible, like NP-complete Problems and Physical Reality. And now this one… https://arxiv.org/abs/1108.1791 all i ever wanted to know about the intersection of quantum computing, cosmology, complexity theory etc
can NP-complete problems be solved efficiently in the physical universe? All hunches would say no, but then we only discovered polynomial time factorization using quantum algorithms 10 years ago.
2011-08-12: Markets being efficient and P != NP can’t both be true, it turns out. So either you can compute fast or make money on the stock market. It remains unclear whether you can MAKE MONEY FAST or not. 2017-01-04: The history of P != NP
In 1955, John Nash sent a remarkable letter to the National Security Agency, in which—seeking to build theoretical foundations for cryptography—he all but formulated what today we call the P=?NP problem, considered one of the great open problems of science. Here I survey the status of this problem in 2017, for a broad audience of mathematicians, scientists, and engineers. I offer a personal perspective on what it’s about, why it’s important, why it’s reasonable to conjecture that P≠NP is both true and provable, why proving it is so hard, the landscape of related problems, and crucially, what progress has been made in the last half-century toward solving those problems. The discussion of progress includes diagonalization and circuit lower bounds; the relativization, algebrization, and natural proofs barriers; and the recent works of Ryan Williams and Ketan Mulmuley, which (in different ways) hint at a duality between impossibility proofs and algorithms.
2022-12-03: Why are there complete problems, really?
This, then, is how universality of computation explains the existence of complete problems. For virtually any class we might define there will be a way of handicapping the universal computer such that it is still able to solve all of the problems in the class while at the same time not breaking the class specific resource constraint.
We can now see that the existence of complete problems is a direct result of one of the core features of computers that also makes them relevant to the real world.
a science fiction novel by Greg Egan which explores quantum ontology via the various philosophical aspects of artificial life and simulations of intelligence
The more science tells us about the world, the stranger it looks. Ever since physics first penetrated the atom, early in this century, what it found there has stood as a radical and unanswered challenge to many of our most cherished conceptions of nature. It has literally been called into question since then whether or not there are always objective matters of fact about the whereabouts of subatomic particles, or about the locations of tables and chairs, or even about the very contents of our thoughts. A new kind of uncertainty has become a principle of science.
The final episode shows how in 1995 Edward Witten of Princeton’s Institute for Advanced Study, aided by others, revolutionized string theory by successfully uniting the 5 different versions into 1 theory that is cryptically named “M-theory,” a development that required a total of 11 dimensions. But the new 11th dimension is different from all the others, since it implies that strings can come in higher dimensional shapes called membranes, or “branes” for short. These possess truly science-fiction-like qualities, since in principle they can be as large as the universe. A brane can even be a universe — a parallel universe — and we may be living in one right now.
I’m not sure that freewill, if it exists, requires any immeasurable quantum mechanical mumbo jumbo. The magic is not in any quantum mechanical phenomena inside the neurons, but in the standard physics arrangement of them.
More likely, the appearance of free will is result of the inability to perform 100% introspection into one’s own mind. I can no more “understand” the real-time machinations of my own mind than a Pentium processor can run a real-time simulation of its own transistors. Because I can’t perfectly introspect my subconscious, much of its output looks magically non-deterministic (hence the seeming similarity to quantum mechanical systems).
Any bounded-rational being would believe itself to have freewill based on its ability to take independent actions and its inability to introspect out all the causal factors underpinning its own actions. In reality, the system that creates intelligence can be 100% deterministic, just too complex for that intelligence to understand itself. Only a much more powerful intelligence could look down and see that these beings that think they have free will are actually operating on “simple” rules.
2007-03-23: Selecting for Gay Pagan Babies. Delicious logical quandaries.
Would the selection rob the child of free will? I don’t think so. What is being set is parts of personality traits, not the thoughts or reactions of the emerging person. They will bias and affect the thoughts, but no more and no less than any other personality traits. That these ones were selected does not give the parents more control over the child or predetermine its destiny. A theological argument against would be that God would make sure to give the right genome, and that parents should trust God to do it right. But if that is true, then God seems to like gays too.
2009-04-16: Strong Free Will Theorem. If indeed we humans have free will, then elementary particles already have their own small share of this valuable commodity. 2014-10-03: The free-will fix
New brain implants can restore autonomy to damaged minds, but can they settle the question of whether free will exists? If free will could be safely enhanced, would those with strengthened capacities be held to a higher standard?
We tend to take it for granted that conscious thoughts precede our actions. Indeed, our systems of morality, justice and moral responsibility are based on the notion that people are free to make thoughtful decisions. However, the US scientist Benjamin Libet’s groundbreaking 1980s experiments on the relationship between brain activity, conscious thoughts and physical actions caused some scientists and philosophers to rethink the concept of ‘free will’ and ask whether our decisions are made subconsciously before we’re even aware of them.
Quantum computing theorist, popular author, blogger, and scientist Scott Aaronson on the #MeaningOfLife, Enlightenment, Schrodinger, Heisenberg, the Matrix, balancing work and family, and why the universe is not just a simulation.
It is becoming increasingly clear that, if a useful device for quantum computation will ever be built, it will be embodied by a classical computing machine with control over a truly quantum subsystem, this apparatus performing a mixture of classical and quantum computation. This paper investigates a possible approach to the problem of programming such machines: a template high level quantum language is presented which complements a generic general purpose classical language with a set of quantum primitives.
A very interesting paper, basically stating that any quantum computer will need a classical front end to deal with data pre- and post processing. even the very pragmatic distinction between call-by-value and call-by-reference needs to be rethought:
It is well known that the no-cloning theorem excludes the possibility of replicating the state of a generic quantum system. Since the call-by-value paradigm is based on the copy primitive, this means that quantum programming can not use call-by-value; therefore a mechanism for addressing parts of already allocated quantum data must be supplied by the language.
2007-02-12: D-Wave 16 qubit prototype, with hopes for a 1024 qubit system in late 2008. funny: they are not sure if it is a quantum computer at all, it might be an analog computer. 2007-04-22: the quantum computation version of the stacked turtle
But it was still pretty exciting stuff. Holy Zarquon, they said to one another, an infinitely powerful computer? It was like a 1000 Christmases rolled into 1. Program going to loop forever? You knew for a fact: this thing could execute an infinite loop in less than 10 seconds. Brute force primality testing of every single integer in existence? Easy. Pi to the last digit? Piece of cake. Halting Problem? Sa-holved.
They hadn’t announced it yet. They’d been programming. Obviously they hadn’t built it just to see if they could. They had had plans. In some cases they had even had code ready and waiting to be executed. One such program was Diane’s. It was a universe simulator. She had started out with a simulated Big Bang and run the thing forwards in time by 13.6b years, to just before the present day, watching the universe develop at every stage – taking brief notes, but knowing full well there would be plenty of time to run it again later, and mostly just admiring the miracle of creation.
For “generic” problems of finding a needle in a haystack, most of us believe that quantum computers will give at most a polynomial advantage over classical ones.
2011-01-20: 10b qubits is very significant. i am sure there are all sorts of caveats, but still: wow 2011-10-04: Philosophy and Theoretical Computer Science class by Scott Aaronson.
This new offering will examine the relevance of modern theoretical computer science to traditional questions in philosophy, and conversely, what philosophy can contribute to theoretical computer science. Topics include: the status of the Church-Turing Thesis and its modern polynomial-time variants; quantum computing and the interpretation of quantum mechanics; complexity aspects of the strong-AI and free-will debates; complexity aspects of Darwinian evolution; the claim that “computation is physical”; the analog/digital distinction in computer science and physics; Kolmogorov complexity and the foundations of probability; computational learning theory and the problem of induction; bounded rationality and common knowledge; new notions of proof (probabilistic, interactive, zero-knowledge, quantum) and the nature of mathematical knowledge. Intended for graduate students and advanced undergraduates in computer science, philosophy, mathematics, and physics. Participation and discussion are an essential part of the course.
2013-04-13: Quantum computing since Democritus. Written in the spirit of the likes of Richard Feynman, Carl Sagan, and Douglas Hofstadter, and touching on some of the most fundamental issues in science, the unification of computation and physics. kind of like a new kind of science was, without the bs. Plus Scott is a funny guy, so even if you only understand 5% (likely, given the deep topics), seems worth it. If you want to get a taste, try this paper: NP-complete Problems and Physical Reality 2017-07-09: Multi-colored photons
the technology developed is readily extendable to create 2-quDit systems with more than 9000 dimensions (corresponding to 12 qubits and beyond, comparable to the state of the art in significantly more expensive/complex platforms).
2018-10-09: Quantum Verification. How do you know whether a quantum computer has done anything quantum at all?
After 8 years of graduate school, Mahadev has succeeded. She has come up with an interactive protocol by which users with no quantum powers of their own can nevertheless employ cryptography to put a harness on a quantum computer and drive it wherever they want, with the certainty that the quantum computer is following their orders. Mahadev’s approach gives the user “leverage that the computer just can’t shake off.” For a graduate student to achieve such a result as a solo effort is “pretty astounding”. Quantum computation researchers are excited not just about what Mahadev’s protocol achieves, but also about the radically new approach she has brought to bear on the problem. Using classical cryptography in the quantum realm is a “truly novel idea. I expect many more results to continue building on these ideas.”
space-time achieves its “intrinsic robustness,” despite being woven out of fragile quantum stuff. “We’re not walking on eggshells to make sure we don’t make the geometry fall apart. I think this connection with quantum error correction is the deepest explanation we have for why that’s the case.”
That rapid improvement has led to what’s being called “Neven’s law,” a new kind of rule to describe how quickly quantum computers are gaining on classical ones. Quantum computers are gaining computational power relative to classical ones at a “doubly exponential” rate — a staggeringly fast clip. With double exponential growth, “it looks like nothing is happening, nothing is happening, and then whoops, suddenly you’re in a different world.”
This is certainly the most extreme of the nerd rapture curves i have seen:
the very near future should be the watershed moment, where quantum computers surpass conventional computers and never look back. Moore’s Law cannot catch up. A year later, it outperforms all computers on Earth combined. Double qubits again the following year, and it outperforms the universe.
In the mid-2000s there was a small diamond mined from the Ural Mountains. Is was called the ‘magic Russian sample. The diamond was extremely pure—almost all carbon, which isn’t common but with a few impurities that gave it strange quantum mechanical properties. Now anyone can go online and buy a $500 quantum-grade diamond for an experiment. The diamonds have nitrogen impurities—but what Schloss’s group needs is a hole right next to it, called a nitrogen vacancy. Russian “magic diamonds” can hold qubits in place and thus act the same way that a trapped-ion rig does. They replace a single carbon atom in a diamond’s atomic lattice with a nitrogen atom and leaving a neighboring lattice node empty, engineers can create what’s called a nitrogen-vacancy (NV) center. This is generally inexpensive since it’s derived from nature.
With no evaluative judgment attached, this is an unprecedented time for quantum computing as a field. Where once faculty applicants struggled to make a case for quantum computing (physics departments: “but isn’t this really CS?” / CS departments: “isn’t it really physics?” / everyone: “couldn’t this whole QC thing, like, all blow over in a year?”), today departments are vying with each other and with industry players and startups to recruit talented people. In such an environment, we’re fortunate to be doing as well as we are. We hope to continue to expand.
2019-07-26: Quantum hardware should make monte carlo methods more powerful & accurate. 2019-08-20: 1 Million Qubits
Fujitsu has a Digital Annealer with 8192 Qubits and a 1M qubit system in the lab. Digital Annealer is a new technology that is used to solve large-scale combinatorial optimization problems instantly. Digital Annealer uses a digital circuit design inspired by quantum phenomena and can solve problems which are difficult and time consuming for classical computers.
Microsoft is developing Majorana-based topological quantum computer qubits which will be higher-quality and lower error rate qubits. A high-quality hybrid system made of InSb nanowires with epitaxial-grown Al shells has revealed ballistic superconductivity and quantized zero-bias conductance peak. This holds great promise for making the long-sought topological quantum qubits.
they have made the simulation of the quantum electrons so fast that it could run extremely long without restrictions and the effect of their motion on the movement of the slow ions would be visible
Transparent crystals with optical nonlinearities could enable quantum computing at room temperature by 2030
2020-12-03: BosonSampling. A second method achieves quantum supremacy.
Do you have any amusing stories? When I refereed the Science paper, I asked why the authors directly verified the results of their experiment only for up to 26-30 photons, relying on plausible extrapolations beyond that. While directly verifying the results of n-photon BosonSampling takes ~2n time for any known classical algorithm, I said, surely it should be possible with existing computers to go up to n=40 or n=50? A couple weeks later, the authors responded, saying that they’d now verified their results up to n=40, but it burned $400000 worth of supercomputer time so they decided to stop there. This was by far the most expensive referee report I ever wrote!
2021-12-06: Quantum Computing Overview. A really good overview of the field of quantum computing with a clear explanation of how they work, why people are excited about quantum algorithms and their value, the potential applications of quantum computers including quantum simulation, artificial intelligence and more, and the different models and physical implementations people are using to build quantum computers like superconducting devices, quantum dots, trapped ions, photons or neutral atoms, and the challenges they face.
Here we report the measurement of logical qubit performance scaling across several code sizes, and demonstrate that our system of superconducting qubits has sufficient performance to overcome the additional errors from increasing qubit number. We find that our distance-5 surface code logical qubit modestly outperforms an ensemble of distance-3 logical qubits on average, in terms of both logical error probability over 25 cycles and logical error per cycle ((2.914 ± 0.016)% compared to (3.028 ± 0.023)%). To investigate damaging, low-probability error sources, we run a distance-25 repetition code and observe a 1.7 × 10−6 logical error per cycle floor set by a single high-energy event (1.6 × 10−7 excluding this event). We accurately model our experiment, extracting error budgets that highlight the biggest challenges for future systems. These results mark an experimental demonstration in which quantum error correction begins to improve performance with increasing qubit number, illuminating the path to reaching the logical error rates required for computation.
2023-06-19: It might be possible to work around noise, making quantum computing practical.
IBM physicist Abhinav Kandala conducted precise measurements of the noise in each of their qubits, which can follow relatively predictable patterns determined by their position inside the device, microscopic imperfections in their fabrication and other factors. Using this knowledge, the researchers extrapolated back to what their measurements — in this case, of the full state of magnetization of a 2D solid — would look like in the absence of noise. They were then able to run calculations involving all of Eagle’s 127 qubits and up to 60 processing steps — more than any other reported quantum-computing experiment. The results validate IBM’s short-term strategy, which aims to provide useful computing by mitigating, as opposed to correcting, errors. Over the longer term, IBM and most other companies hope to shift towards quantum error correction, a technique that will require large numbers of additional qubits for each data qubit.
Gregor J. Rothfuss 