21 ms·

Scott’s Supreme Quantum Supremacy FAQ

603 points by xmmrm 7y ago

nexuist 7y ago
Preface: I know nothing about quantum computing. What exactly is a qubit? I'm not asking what does it mean, because I know there's superpositions and all that jazz, but as in...like, in an electronic circuit, what is a qubit? Is it made out of logic gates? Which ones? If we can make one qubit, can't we just make a bunch of them by copy and pasting circuits similar to how we used vacuum tubes in the 60s and 70s? How come our current limit is only around 54 or so? Are qubits, and quantum computers by extension, not even electronic circuits? If so...what the hell are they?
- Analemma_ 7y ago
  Just like a bit, a qubit is an abstract representation of information, which can be physically instantiated in different ways.
- freeone3000 7y ago
  You can do it with electron spin or photon polarization or by any number of properties, but it's the state of a fundamental particle. It's an entirely new type of computing apparatus, using the fundamental state of particles. No electron circuits, those won't work. And it's expensive because of the above. These things are massive, have to be kept at cyrogenic temperature, and isolation gets harder the more particles you have.
  - drdeca 7y ago
    I thought a qubit could also be implemented with current going around a superconductor loop. Is that incorrect?
    - ben_w 7y ago
      You can implement them like that. Anything that has a quantum state that doesn’t decohere too fast will work. The hard part thus far has been that almost everything does decohere too fast.
    - Denvercoder9 7y ago
      No, that's indeed a quite popular approach.
- rolltiide 7y ago
  I'm in the same boat. A qubit can have more than the two states that a transistor can have, got it. Okay, now what can we do with that? "crack encryption by simulating a state!" yeah but what? is that something I should be concerned about now? "hahaha no no no silly normie we'd need two thousand qubits for that, this machine only has 53!" oooookay, and you did that number in your head, how??? "we just solved the first unsolvable problem that a mere bit bound supercomputer couldn't solve, look at this math formula!" but that didn't explain "we are celebrating, are you not celebrating" There just seems to be a lack of non-introductory but non-PhD level information. Where is the "explain it like I've been accepted into college at all".
  - rmidthun 7y ago
    Since we're looking at Scott Aaronson, you might want to check out "Quantum Computing Since Democritus". It gives a good explanation of the math behind qubits and how they can be used. Best intro I know of.
    - rolltiide 7y ago
      thank you for that and not trying to explain it in an additional convoluted way
  - rini17 7y ago
    Schrodinger's cat in unopened box is 1 qubit = it's alive and dead at the same time. When the box is opened to observe the result, the quantum state "decoheres" - decays to 1 bit result. Now imagine 53 such boxes, interconnected by quantum gates. The 53 qubits combined are in all of 2^53 states at once. The gates can be set up such that some combinations like "cat 1 alive", "cat 2 dead", etc. are much more likely result than others, after the boxes are opened. And all this computation is done in one step, whereby the classical computer must do 2^53 steps to get the same result. To have 53 cats all undisturbed in these dead/alive states so that computation is done without errors is very technically challenging :)
    - drdeca 7y ago
- buboard 7y ago
  for example an electron or a polarized photon. they can take the value 0 and 1 when measured but when not measured they can be in superposition states. Quantum physics forbids copying a qubit to create another, but you can initialize them en masse to to be in a superposition state. Those things are too tiny to be easily manipulated so 53 is quite an accomplishment.
  - AgentME 7y ago
    >>If we can make one qubit, can't we just make a bunch of them by copy and pasting circuits similar to how we used vacuum tubes in the 60s and 70s? How come our current limit is only around 54 or so? >Quantum physics forbids copying a qubit to create another, but you can initialize them en masse to to be in a superposition state. Those things are too tiny to be easily manipulated so 53 is quite an accomplishment. Quantum physics forbids copying the value of a qubit, but the poster was asking why we couldn't just make more of the device that implements a qubit. The big issue is that you want the qubits to be entangled together and it's hard to prevent decoherence as you make a larger device with more qubits.
- itcrowd 7y ago
  Essentially, they use superconducting electronics to create a quantum circuit. It's not the same logic gates as a traditional computer chip and not based on the same physics. The details are difficult & messy. There are several reasons it doesn't scale easily to more qubits, but you can imagine that you don't want the chip to be large (must be cooled to 25mK!) but the qubits should be spaced quite far apart so they don't influence each other. Also, it's not a very simple circuit, so the layout of the transmission lines ("wire on a chip") becomes difficult to manage. The last problem also scales badly with the number of qubits (the middle qubit becomes progressively harder to reach). There is a paragraph in the (leaked) paper that describes their chip: > In a superconducting circuit, conduction electrons condense into a macroscopic quantum state, such that currents and voltages behave quantum mechanically [2, 30]. Our processor uses transmon qubits [6], which can be thought of as nonlinear superconducting resonators at 5 to 7 GHz. The qubit is encoded as the two lowest quantum eigenstates of the resonant circuit. Each transmon has two controls: a microwave drive to excite the qubit, and a magnetic flux control to tune the frequency. Each qubit is connected to a linear resonator used to read out the qubit state [5]. If you want a physical picture, check out [6]: https://arxiv.org/abs/cond-mat/0703002 https://arxiv.org/abs/cond-mat/0703002 edit: source [6] is more appropriate and open to access
  - outworlder 7y ago
    Holy hell. > > In a superconducting circuit, conduction electrons condense into a macroscopic quantum state, such that currents and voltages behave quantum mechanically [2, 30]. Our processor uses transmon qubits [6], which can be thought of as nonlinear superconducting resonators at 5 to 7 GHz. The qubit is encoded as the two lowest quantum eigenstates of the resonant circuit. Each transmon has two controls: a microwave drive to excite the qubit, and a magnetic flux control to tune the frequency. Each qubit is connected to a linear resonator used to read out the qubit state [5]. I understand most of the words in isolation – and I know that they are valid, even if combining them in a useful manner to understand exactly what they are describing is eluding me. But if there was ever a paragraph that sounded like pure technobabble, this is it. Replace the technobabble found in the star trek matter transporter with quantum lingo, and it would sound very similar.
- diegoperini 7y ago
  > What exactly is a qubit? A bit is like a boolean type, has the values of true and false. Or you treat those values as 0 or 1, then gather a bunch of bits to build useful numbers. A qubit is like a pair<number, number> such that these numbers MUST satisfy the following constraints: pair.left^2 + pair.right^2 = 1 pair.left and pair.right can be any complex number Why such a composite type with weird constraints you may ask? Because that's how properties of really small particles behave in the real world. So the hope is, maybe if we can build our software using this weird data type called qubit, we can implement computation on quantum hardware without abstracting every problem using a dump type like a boolean or its aliases/collections. Remember that classical computers use a clock to flip bits over time. A similar quantum computer would manipulate qubits instead. A bit has the storage capacity of 2 distinct bits of information. A qubit has the storage capacity of 2 complex numbers, which corresponds to 4 floats, which is at least 16*8 bits of information if we are conservative about our assumptions. > Is it made out of logic gates? Kind of. Most of the current logic gates are built with semiconductors. It means by applying different voltages/currents/flux etc to different parts of a solid material, we can alter what we measure in some other part of the same material. A quantum logic gate uses the same principle but in order to achieve the desired speed and storage advantages, it uses an object with a measurable property that at least approximately behaves like a quantum mechanical object. Common semiconductors are too crowded of atoms in terms of their body parts to make good quantum materials. They touch to each other and are almost always exposed to air. Their running temperatures are undesirably high. A really dark (literally without a single photon) vacuum chamber that holds a really small amount of floating matter in the middle, frozen with lasers up to 0.000...1 Kelvin would make a good example of a stable but expensive qubit. We can measure this qubit by destroying its state, i.e by applying a magnetic field and measuring the emitted photon's location, polarization or frequency. The problem is, copy pasting this device to build a circuit is really hard due to logistics and auxiliary machinery required to keep all the state stable. > How come our current limit is only around 54 or so? That's not a fundamental limit but an engineering one, due the issues I mentioned above. The bigger the device gets, the harder to maintain its stable state. The method currently used for reaching this limit really looks like what is used in the 60s. History is repeating itself with a small twist, the running temperature is extremely low this time. Not liquid nitrogen low, but compressing atoms by sniping them from distance via laser on multiple directions low. There is also one more problem that is unique to quantum computers. You have to measure the same qubit multiple times to be able to read those complex numbers since their values are determined statistically. You either represent a qubit with multiple qubit like devices or you use the same device to try your measurement repeatedly. Each approach comes with its own drawbacks. > Are qubits, and quantum computers by extension, not even electronic circuits? Even today, non quantum circuits are sometimes non electronic in some of their parts. Fiber optics, supersonic emitters/receivers and photoelectric sensors are good examples. To this day, it is not clear whether the first consumer quantum CPU will be entirely electronic or not.
- raincom 7y ago
  "[T]hose believing that a QC can manipulate or maintain huge objects "free of cost" (i.e., at unit cost) should provide a convincing explanation to this fantastic speculation. Being skeptic of this (rather over-simplified and counter-intuitive) speculation seems to be the default and natural position." (From http://www.wisdom.weizmann.ac.il/~oded/on-qc.html http://www.wisdom.weizmann.ac.il/~oded/on-qc.html )
- 3PS 7y ago
  Short answer, a qubit is a unit vector in a 2D complex Hilbert space. Now, that doesn't actually say much about why we care or how they're useful. In practical terms, you can think of qubits as complex unit vectors along two axes, with one axis corresponding to |0⟩ (the zero qubit) and one axis corresponding to |1⟩, or the one qubit. So for example, you could have a qubit called |+⟩, which is just shorthand for (|0⟩ + |1⟩)/sqrt(2). Measuring a qubit in a basis collapses it to one of the basis vectors (e.g Schrödinger's cat must be alive or dead once we open the box) with probability equal to its inner product with that basis vector. This is why we need a Hilbert space and not just any old vector space. Finally, to answer your question about gates, a quantum gate is basically a unitary matrix, i.e. a matrix that preserves the norm of its inputs. You can feed qubits into these matrices by themselves or, more often, many at once, by using something called the tensor product of the qubits - this is where the math gets slightly more involved. The long and short of it is that we can induce correlation patterns between qubits using these gates (aka quantum entanglement) and orchestrate circuits of interference patterns where the wrong answers cancel each other out and the right answer gets reinforced so that we measure it at the end - unfortunately, this is where my knowledge breaks down as a beginner. My apologies if I accidentally handwaved anything important but hopefully you get the gist.
  - galaxyLogic 7y ago
    > Schrödinger's cat must be alive or dead once we open the box I recently had a conversation about this in another thread. It seems to me, and nobody tried to convince me otherwise, that the Cat would be the Observer. Therefore it would be dead, NOT dead AND alive, as soon as it observes the poisonous gas in its box.
    - 3PS 7y ago
      So this is a little nuanced. It's true that quantum systems collapse on "observation", but that doesn't actually mean "observation by a sentient entity". It could really just be any interaction with the outside environment. (This is why qubits have to be kept incredibly well-isolated.) We don't really fully know exactly how this collapse works, and related speculation is generally classified under the measurement problem [1]. But it's true that one of the key points of Schrödinger when proposing his thought experiment was that the notion of measurement or observation was not fully defined under the Copenhagen interpretation. Side note, it's not that the cat is observing poisonous gas, but rather, that a Geiger counter is set to detect whether a radioactive atom decays or not and triggers the release of some poisonous gas if so. So, classically, Schrödinger's cat would be either alive or dead 50% of the time, not 100% dead. There are plenty of alternative ways to reconcile this classical view with quantum mechanics. Perhaps the simplest and most well-known is the many-worlds interpretation [2], which states that both events occur, just in different timelines, and we don't know what timeline we ended up in until we open the box. (Of course, it is ridiculous to speculate as to which timeline "we" end up in before the experiment is carried out, because the people in both timelines would still be "us" - this can get awkward to think about.) [1] https://en.wikipedia.org/wiki/Measurement_problem https://en.wikipedia.org/wiki/Measurement_problem [2] https://en.wikipedia.org/wiki/Many-worlds_interpretation https://en.wikipedia.org/wiki/Many-worlds_interpretation
- cdumler 7y ago
  TL;DR: A quantum computer is a device that uses the measurement of quantum properties to do computation. There are many ways to implement one depending on the type of entangled particles being used, from crystals to make entangled photons and superconducting mounds to entangle electrons. This is the same for binary computers, which can made from electrical devices (transistors), values with air pressure or balls falling down wooden ramps. Longer version An observation about quantum behavior is that there are only certain properties that you can measure for the really, really small. These include things like mass (total energy), charge (intrinsic amount of electromagnetic strength), and spin (willingness to change direction in the presence of an electromagnetic field). It turns out that when you measure these properties, the measurements behave in non-intuitive ways. The act of measuring the spin of a particle (which could be in any direction) is really the act of asking, "is this particle aligned with my detector?" The result will always be either aligned up or aligned down. It will be randomly about 50/50 up and down, also. This is not that surprising because the spin must align one direction or the other. The crazy part comes with the fact that you can entangle two particles. Entangle particles can be sent off through different detectors and one thing will always be true: while any particular outcome is random, the detectors will always generated opposite results. The temptation is to say, "well, they were generated from the same source, so they have just opposite starting positions." Long story short, this has been proven not possible. Instead, there is some fundamental behavior is quantum mechanics that says that there are certain types of activities with entangles particles that have a correlation that is true as long as the entangle particles are not disrupted. In this case, particles sent to separate detectors will always have opposite results. A quantum computer uses these correlation truths about measurements to do computations. A qubit is the concept of a quantum bit: an entity that represents one unit of entanglement. Just like a bit, quantum computers have many different ways to implement entanglement. You can entangle photons, electrons, and whole atoms. Each of these systems require specific implementations to achieve, like like electronic or mechanical computers. Remember that one detail about "if they are not disrupted?" Yeah, turns out that it takes a hell of a lot to create an environment that doesn't destroy the coherence of the entanglement. You have to design something that allows you to setup the particles into starting state, be able to hold those particles in an entangled state with no disruptions and have a detector to determine the final state. Quantum mechanically, these are generally opposite goals.
- tagrun 7y ago
  Physicists here. In practice, a qubit is a two-level physical system. It can be spin state of an electron, polarization of a photon, lowest two energy states of an atom or an electron in quantum dot/well trap potential, the charge state (called charge qubit) -- whether you have 0 or 1 electrons in it, etc etc (if you have 3 levels, it's called qutrit, and for d levels qudit). This experiment uses charge qubits (a special variant which has some robustness against charge noise by design [by operating at a voltage level which is insensitive to 1st order fluctuations in the electric field, called "sweet spot"], called transmon). The main problem is achieving full control of these systems, which is extremely hard, because there are certain things (some random/stochastic) that you can't control at all and you have to fight+race against their influence: - qubits are tiny, and the energy splitting between these two states are typically minuscule: this means even a small vibration from a sneeze miles away can make the qubit flip. - qubits do not live in vacuum, they are typically hosted in solid-state systems and the qubits are coupled to their hosting environment, which have their own moving parts (two-level fluctuators which lead to charge noise, phonons which also couple to electrons typically via spin-orbit coupling, spinful defects in the material which have their own dynamics, etc etc) that you can't really control. it's extremely difficult to achieve full control of a qubit in the presence of things that you can't control and random in nature. - if the qubit is the lowest two-levels of a system with higher energy levels, one also needs to worry leakage errors to those higher states - there are ways of suppressing the influence of such unwanted interactions (dynamically corrected gates + quantum error correction codes) given that their strength is below certain thresholds. going below those thresholds is again an enormous engineering/material science problem (extremely low temperatures, isolation from vibrations, low/high-pass filters for the classical circuitry which is used to control/drive the qubits via electric/magnetic fields, design of the device itself which typically hosts two-level fluctuators, etc etc). this problem becomes harder in general as you increase the number of qubits though. - to do anything non-trivial, you need to have more than one-qubit and have controllable couplings between those (so you can't put them apart too far which makes it impossible to couple them). this doesn't work perfectly in practice, you can't completely control or turn off their couplings (a problem called cross-talk) which again leads to errors. so it doesn't work quite like modular classical circuit elements which you can "copy & paste" because the abstractions from the low-level, nitty-gritty physics of the underlying material fail for all these qubits.
- justinpombrio 7y ago
  > If we can make one qubit, can't we just make a bunch of them by copy and pasting circuits similar to how we used vacuum tubes in the 60s and 70s? How come our current limit is only around 54 or so? This is a very good question! And as far as I can tell, no one has actually answered it yet. In classical physics, which suffices to explain circuits made of vacuum tubes, the state of a system is fully captured by the states of its parts. Like, if you want to know the state of three bits, I just have to tell you what the first bit is (0 or 1), and the second bit, and the third one. Basically everything we interact with has this property: if you fully describe the state of each part of a thing, you have described the state of the whole thing. But quantum mechanics is... weirder than this. In quantum mechanics, to describe the state of a system you have to give one complex number per classical state, such that the sum of the squares of the absolute values of the complex numbers adds up to 1. These complex numbers roughly correspond to the "probability" that the system is in that state (but not quite, it's more complicated than that). So in quantum mechanics, to describe the state of three bits, you have to give eight complex numbers n1,n2,...,n8, one for each of the classical states of the bits 000, 001, 010, 011, 100, 101, 110, 111, where the sum of the squares of the absolutely values of n1,...,n8 add up to 1. That's a lot more information than 3 bits. (Imaging if you had 54 bits... you'd need 2^54 ~= 10^17 complex numbers to describe them.) Technically, everything in the whole world, including you, is described by the laws of quantum mechanics. So why don't we see weird quantum effects all of the time? Quantum systems are very fragile: whenever they interact with the outside world (say a photon from the air bounces off of something in the system), the system "collapses", and then behaves as classical physics would predict. (Note that this is in accordance with the quantum prediction. The system goes from "only describable using difficult quantum mechanics" to "describable using quantum mechanics, but it'll just say the same thing as classical physics, and classical physics is simpler so you should just use that".) So here's what a qbit is: it's just a regular bit that has been so insulated from the outside world that classical physics doesn't suffice to describe it. You won't find qbits on a regular circuit board, though, because they'll interact with the circuit board in any way whatsoever and then you're done. And this is why making a 54-qbit quantum computer is so hard. You need to keep all of the qbits isolated, because if any of them interact with the outside world (think the air in the room, or a single photon, or the substrate that the qbits are on), then the whole system "collapses".
- grumpy8 7y ago
  Extremely simplified: >> in an electronic circuit, what is a qubit? It's not an electronic circuit, it literally is an electron or a photon. And it's using that particle's properties to do "superposition and all that jazz". You can't put too many next to each others because they start interacting together because that's what electrons do when they get close.
  - deleted 7y ago
    [deleted]
- tzs 7y ago
  > If we can make one qubit, can't we just make a bunch of them by copy and pasting circuits similar to how we used vacuum tubes in the 60s and 70s? How come our current limit is only around 54 or so? (I'm not an expert in this area, so the following may not be incomplete or limited to only certain kinds of quantum computation, or worse). The kinds of computation that qubits can beat a classical computer on require that the qubits be entangled. If the qubits are not entangled, you can't do better than regular bits. Briefly, if two (or more) quantum systems are entangled, and you make certain measurements that have a random outcome on one of the systems, and then measure the same property on the other system(s), there will be correlations that you would not get if the systems were not entangled. The entangled systems act is if whenever you measure one and it randomly chooses a value for the property you measured, that result is somehow communicated to the other entangled systems, and they make sure them that when they are measured they will give results with the appropriate correlation. You might think that this could be explained if the systems had some internal variables that were set when they became entangled that determined what "random" values they would pick when later measured, but there are experiments that have shown that this is not so. The systems are truly making their random choice at the time of measurement as far as we can determine. This happens even if after you entangled the systems, you separate them by a great distance--so far that between the time you do the measurements on the separate systems there is no time for any communication between the systems (or, rather, no time for any communication limited by the speed of light--I believe there have been experiments showing that IF there is communication, it is at more than 10000 times the speed of light). (This communication, or whatever it is, cannot be used to send messages faster than light. All it can do is make the correlations work out for entangled systems). Anyway, the thing about entangled systems is that as soon as you make a measurement of the entangled property, you lose the entanglement. Your particle that had entangled spin, say, with another particle and that was 50/50 whether it was spin up or spin down becomes, once you actually measure spin, a non-entangled particle whose spin is a concrete value, either up or down. Measure it again, and you get the same value. When I say "you make a measurement", I don't specifically mean you, or any other human, or any human instruments. For purposes of quantum mechanics, a measurement is anything that makes the system reveal a value. So if you have a particle with entangled spin with some other particle, and some random passing particle happens to interact with yours in a way that depends on the spin of your particle--that's a measurement and you've lost your entanglement. (Your particle might now be entangled with that random passing particle, but it is no longer entangled with the particle you intended it to be entangled with). If you are trying to do a quantum computation on 50 qubits, you have to get them all entangled, and then you have to keep them from interacting with anything that might inadvertently do a measurements long enough for them to do their quantum computation, where you can then measure the result (which finally ends the entanglement). This turns out to be hard, because there are a lot of things in the universe that want to effectively do a measurement. Any random particle bumping into one of yours with too much energy can do it. Some random passing electromagnetic wave can do it. The more things you need to entangled and keep entangled, the hard this is, and 50ish is the current limit.
- sundarurfriend 7y ago
  Quantum computing for the very curious [1] has been very useful to me, for getting at least a basic idea as to what exactly a quantum computer is, what a qubit is, and how they are manipulated. [1] https://quantum.country/qcvc https://quantum.country/qcvc
ClintEhrlich 7y ago
I've been waiting for Scott Aaronson to put all of this into perspective since the first leaks about Google's quantum supremacy started appearing in popular media. He has exceeded my expectations with this post, which cuts through all the hype to communicate exactly what the results of this experiment mean for the field. It's worth reading and sharing.
- ClintEhrlich 7y ago
  On second reading, I have but one trivial gripe: "Enormity" implies moral reprobation, so it's a poor way of describing the significance of a computational discovery.
  - klipt 7y ago
    Isn't it just Enormous : enormity :: huge : hugeness?
    - ClintEhrlich 7y ago
      Not quite. Enormous : enormousness :: huge : hugeness. Enormity = Immense scale of evil (e.g., the "enormity of the holocaust")
      - alanbernstein 7y ago
        Thanks for the enlightening nitpick, this is one of those terrible/terrific things about English that I love/hate.
      - andrewflnr 7y ago
        As a native English speaker, I can't say I've found this to be the case. "Enormity" does tend to be used for dramatic effect, most often on moral issues, but I don't think that makes Scott wrong to use it here. I don't know if I've seen "enormousness" before this thread.
        7y ago
whatshisface 7y ago
If it goes well, the history of quantum computing will be divided up in to three eras: the era of twisty philosophical arguments that it's working ("the molecule is simulating itself"), the era of academic arguments that it's working ("we can solve this one carefully constructed problem") and the era of practical arguments ("Amazon is selling QC time for $20/kilogate-bit, what do you mean it's not possible?"). Quantum supremacy marks the transition from the first era to the second.
- p1necone 7y ago
  I really enjoy seeing comments on here that fit the 3rd kind. "Thing is ridiculous, that could never work because of reasons A, B and C." "What are you talking about, here is project that does thing, it functions perfectly." Nothing like reality proving someones baseless naysaying wrong immediately.
  - smsm42 7y ago
    Except reality has so far proved that it is possible to use QC for solving one QC-specific task that is hard to solve classically, that's it. That's not what "naysaing" was about - the "naysaying" was about the fact we have no way to use QC for known classical tasks, and the path to such juicy targets as breaking commercial public key encryption is entirely unclear. Virtually nobody says it would never ever happen - but so far it has not happened and will not happen soon, and reality has not proven anything contradicting that yet. When, in 2038 or in 2083, the reality finally gets there, then your condescending attitude towards the naysayers would finally be completely warranted. But not yet.
- gowld 7y ago
  What are the theoretical models for the energy cost of computing on a qubit? I'll be excited for QC when there is known way (even with some handwaving and future-tech plans) to compute a non-trivial result for a reasonable sum, such as "crack someone's private RSA key for under $10M of compute cost"
  - sanxiyn 7y ago
19ylram49 7y ago
Much needed perspective in the age of overly dramatic headlines and straight up misinformation.
age_bronze 7y ago
I posted this on scott's blog, still awaiting moderation: "I’m trying to understand the chain of inference from Google’s leaked result of quantum supremacy to theoretical computer-science “hardness” of the computation. Computing the exact probabilities of a random quantum circuit is proven hard, but computing the exact probability of a random algorithm is also an open problem, so what you really care about is approximation of computing the probability (up to epsilon), or even weaker, just sampling from a probability (also up to epsilon under some metric of comparing distributions). Their computer implements Random Circuit Sampling, and their cited “theoretical” hardness results are your paper from 2017, of QUATH => HOG, and as far as I understood from your paper, proving that approximation / sampling from a (random) quantum computer/circuit is hard is still an open problem (Am I wrong here? I’m not up to date with everything), and a difficult one. But you did make a compelling argument that even if QUATH was solvable, it will lead to new insights. Their actual benchmark uses cross-entropy benchmarking, called xeb in their paper, and defined as 2^n* [P(x_i)] _i-1 (Can’t type brackets). I could not find any ‘theoretical hardness’ paper at all using this benchmark, some results talk about different XEB using log but they prove these are not strong enough and can be reached classically. Are there any hardness results for their benchmark? I wonder why they would use that instead of the proven HOG, even for smaller input sizes, I would see more value in a benchmark which has theoretical roots. I feel intuitively like their benchmark is much more similar to the log variation of XEB than to HOG, but didn’t think it through completely. As for their gates, I understand they are not general random quantum gates, but instead they have a variation of iSWAP and controlled phase CZ. The hardness results that do exist also don’t address the limited gates, in how it changes the distribution of random circuits. Are those two gates at least universal, so that we have hope that this could be proved? Their statement was “but reliably generating a target unitary remains an active area of research”, so I assume they aren’t universal. I would love to see some heuristic argument as to why those two in particular are hard, especially given results like Gottesman–Knill theorem, it seems like some surprising gates do have classical simulation. iSWAP is just swap and phase gates, and CZ is phase gate only on the 11 state. Doesn’t feel like it could be universal to me but maybe I’m wrong. I probably missed some things, so I’d love it if you could point to papers filling the gaps between their results and a real theoretical statement. I don’t have the intuition to tell which gaps are important and which are not. I also don’t know which papers/results already exist and I can’t really search as I am not an academic, and don’t have full access to many papers, and you probably know the state of the art results. "
codeulike 7y ago
My cat can behave as a cat would be expected to behave. And if we verify the measurements of her behaviour using a classical computing cluster - to make sure her behaviour really falls within the distribution of expected cat behaviour - thats a very complicated calculation that will take many processor-days. But my cat can just do that stuff in real time. Has my cat achieved Quantum Supremacy, and is there a trophy or something I can pick up somewhere for that?
- teraflop 7y ago
  That sounds like question 12 from the FAQ ;)
  - codeulike 7y ago
    Ah yes, indeed. So it hinges on whether my cat is programmable. Well as it happens my cat has a number N of programmable modes: 1 - cat having its ears tickled 2 - cat watching something move under a sheet that might be a mouse 3 - cat waiting for tin of cat food to be opened 4 - cat wanting to get through a door etc etc up to 'N' So a “challenger” generates a random number C between 1 and N, and the challenger then sends C to me and my cat, and I apply the appropriate 'input' to my cat, tickling her ears or openeing a tin of food or whatever, to get her into the correct mode. We then measure her behaviour and then fire up our cluster of computers and run the simulation and then wait for a few months for the numbers to get crunched to verify if the cats behaviour was within expected probability distribution for C.
    - SpicyLemonZest 7y ago
      "Programmable" in this context would mean that you can encode complex computational problems into your cat's behavior. The idea is to distinguish a cat that can only calculate cat behavior (which is of course a very easy problem) from a cat that could eventually be engineered to calculate whatever you want. If you can solve complex computational problems faster than a cat-sized computer by carefully arranging tins of cat food, it would definitely be fair to say your cat computational supremacy is a significant achievement.
westurner 7y ago
Who even asked these questions? I question this. All of this.
- fastball 7y ago
  Literally people on HN have been asking many of these questions for years whenever QC is discussed.
  - westurner 7y ago
    I believe Feynman originally asked the QC question many many years ago. What an exciting milestone and a great FAQ. "Always naysaying! Everything I create!"
bjornsing 7y ago
I have the greatest respect for Scott, but I do think he’s being a bit too enthusiastic here in comparison with the D-wave. At the very least I think he should have included this question in his list: Q: Why can the D-wave not be used to illustrate “quantum supremacy” in a similar way? (As I understand it the D-wave can sample from the solutions to ”ising model-like” problems, which I assume would be extremely difficult for a classical computer to do (but probably possible to verify).)
- rsln-s 7y ago
  Unfortunately, the same complexity considerations do not hold for Ising problems. While many NP-hard problems can be formulated in Ising form, it is often not hard to get a “pretty good” solutions to these problems. DWave and collaborators have spent a decade trying to come up with exactly the same thing as demonstrated here — namely, a problem specifically designed to demonstrate quantum advantage of any sort — and as of now did not succeed. To answer your question specifically: DWave does not allow the same level of control over qubits.
  - bjornsing 7y ago
    I’m aware of D-wave’s struggles, but my impression was that they had failed at finding a “deterministic” problem where they could show quantum advantage. I’ve never heard a claim that whatever probability distribution the D-wave can sample from a classical computer can also sample from. I’d love to read about it if you have a reference!
    - sanxiyn 7y ago
      My understanding is that it is exactly the case D-wave probability distributions can be sampled classically.
- bjornsing 7y ago
  Another reason I feel this is oversold: This quantum “computer” cannot run Shores factorization algorithm. But if it could it would only be able to factor integers up to 2^53. The time required to factor a 2^60 to 2^80 integer on a classical computer is measured in milliseconds [1]... Quantum supremacy in any reasonable sense of the word supremacy is a long way off. 1. https://hal.inria.fr/file/index/docid/451604/filename/smallint_expcomp_draft_02_1.pdf https://hal.inria.fr/file/index/docid/451604/filename/smalli...
calhoun137 7y ago
I think we need to comes to grips with a hard truth about the reality of academic life. Once you invest decades of your life into a research subject, if it turns out the entire thing is never going to work, there are major social and financial pressures to deceive the public about the true nature of the subject. I saw this happen with string theory first hand, and my experience with string theory was a major factor that led to changing paths to pure mathematics and computer science. As someone who has spent a lot of time researching QC, I do not believe it will ever be possible to build a practical quantum computer. We have been over this so many times on this site. Here is a good link from a serious professional who takes the same position [1] In fact, my personal opinion is that quantum computers are functionally, a hoax, the main purpose of which is to generate hype, secure research grants, ensure career stability for academics, and give science reporters something to write about to get clicks while deceiving the public. [1] https://www.quantamagazine.org/gil-kalais-argument-against-quantum-computers-20180207/ https://www.quantamagazine.org/gil-kalais-argument-against-q...
- dcposch 7y ago
  > Once you invest decades of your life into a research subject, if it turns out the entire thing is never going to work, there are major social and financial pressures to deceive the public about the true nature of the subject. You're implying that Scott Aaronson is being deceptive. I think that needs better evidence. The story you linked to is two years old and it's about QC skeptic Gil Kalai. Scott addresses him directly in his post: > If quantum supremacy was achieved, what would it mean for the QC skeptics? > I wouldn’t want to be them right now! They could of course retreat to the position that of course quantum supremacy is possible (who ever claimed that it wasn’t??), that the real issue has always been quantum error-correction. And indeed, some of them have consistently maintained that position all along. But others, including my good friend Gil Kalai, are on record, right here on this blog predicting that even quantum supremacy can never be achieved for fundamental reasons. I won’t let them wiggle out of it now.
  - calhoun137 7y ago
    I am not very familiar with Scott Aaronson and am just making a general observation about the subject of QC, I have no idea what his motivations or intentions are. If Scott believes QC will day be practical and I don't, only time can tell who is right and who is wrong. I have seen this kind of goal post moving in string theory, and its been going on for 20 years with QC in a strikingly similar way imo. There is no way to argue against this kind of goal post moving style of debate because even if another 20 years go by and QC still don't exist on a practical level, the goal posts will just keep getting moved. I am extremely confident that this will continue until the public gets bored of hearing about it.
daxfohl 7y ago
What's e.g. China and Russia doing in this space? Or the US Gov't for that matter? I can't imagine that national governments are just waiting for Google and IBM to do the research and publish their results. Is it possible/likely that NSA or some other national equivalent is way beyond these results already?
- reilly3000 7y ago
  I don't know what the NSA spends on R&D, but I have to imagine they don't have a multi-billion dollar budget for secret R&D facilities and talent. It would seem more likely they are monitoring developments in public and private research and responding opportunistically. I'm just making assumptions here, but also I don't think somebody with clearance could correct me here in public :P
  - daxfohl 7y ago
    I'd think the opposite. I would imagine they have orders of magnitude more to spend on crypto research than a private search engine company (which is why I asked the question originally). But really I have no idea. (If they did then why aren't there job ads etc). And you're right, probably nobody who does have an idea would be able to say.
  - jessriedel 7y ago
    The NSA has the money and a history of massive secret projects. There are more mathematicians at the NSA than in all of academic cryptography. However, my general impression is that most people don't think the NSA has a secret QC project because there hasn't been a noticeable disappearance of the best young experimental QC researchers from the pipeline like there has been for cryptography. It's the promising people quietly leaving that is hard to hide; massive construction projects are comparatively much easier to hide.
    - muraiki 7y ago
      A recent NYT opinion piece from the general counsel of the NSA discusses many of these issues, including quantum computing: https://www.nytimes.com/2019/09/10/opinion/nsa-privacy.html https://www.nytimes.com/2019/09/10/opinion/nsa-privacy.html
billions 7y ago
Most things that get years of speculation and press never come to fruition
- smolder 7y ago
  Like flying machines, speculated about from DaVincis time?
yters 7y ago
Most major breakthroughs were pretty low tech in origin, and the high tech was all about optimizing the idea. I think we get fundamental research backwards nowadays.
- khawkins 7y ago
  At the very least, we shouldn't be comparing quantum computing to air flight. The Wright brothers were basically hobbyists, incomparable to the global leading technology corporations in the history of human civilization. This seems more comparable to the moon landing or LHC Higgs-Boson discovery. Challenging to pull off once, and the next steps seem to increase exponentially in man-power and cost.
  - scottlocklin 7y ago
    I think the proper analogy is controlled nuclear fusion, which google is also dabbling with.
  - yters 7y ago
    Those haven't really brought us much benefit. The benefit to effort relationship seems to be inverse.
person_of_color 7y ago
Where does this put Rigetti Computing?
erichocean 7y ago
> It’s like, if you believed that useful air travel was fundamentally impossible Uh, there are birds. Literally everyone thought useful air travel was possible, and not only possible, but so easy that a Darwinian process was able to produce it, not once, but literally thousands of times, in thousands of ways. ---- But looking at the actual "experiment", I don't count that as computation in any meaningful sense, and morally equivalent to the following: Set up a digital camera and point it at a scene. Take a picture. Now take millions of additional pictures, without moving the camera. Measure the values at each pixel. See how they correspond to "amplitudes"? That's our computation. <= (This is the part of the article that should raise eyebrows...) Article (smugly): How about you simulate (render) the scene using an actual computer? Measure the amplitudes of the resulting millions of images. OMG, that took you so long!!! Loser. Are we being punk'd here? The digital camera is the quantum computer. The "scene" is the random initial state C. The scene is then translated into a renderable scene for the classical computing version, and rendered with an unbiased physically based renderer, which produces the same result. I fail to see how any of this is even remotely exciting, much less interesting. A camera is not a computer, no matter how many measurements you make with it, nor how "random" the scene you are taking pictures of is. And yes, simulating reality takes more cycles than just measuring whatever happened with a camera. Photos are "faster" to get than the equivalently rendered scene—news at 11! Again: Are we being punk'd here?
- core-questions 7y ago
  Perhaps it will make more sense to explain how a D-Wave machine works, as (a) they actually exist and you can use one today for free online, and (b) it's way simpler than a gate model QC is. Imagine a bunch of magnets. Imagine forcing them into a "frustrated" configuration; maybe you have them all on a grid, and you have servomotors that can rotate them to face any way you like. The servomotors are strong, so counteracting the magnetic forces is easy for them. You design an appropriately frustrated configuration, and then release all of the magnets at once. What configuration do they rotate into? A quantum annealer is conceptually similar. Each qubit, on a regular, patterned graph, has connections to its neighbours. You can leave these alone (no corellation) or tune them up to +/- 1, corresponding to "must be the same as this other qubit" and "must be different than this other qubit". You can also bias each individual qubit to be a 0 or a 1. Then, you let it go, and it anneals, and you observe the result. Your goal is to get to the _lowest energy state_ possible: the least possible frustration remaining. In our magnet example, it would be as few magnets as possible wanting to move - if you poked them with your finger they'd want to go back into their current state. You could imagine that your magnets might not get down to their absolute lowest energy state; maybe it would take too much energy to flip from their starting state to that lower state. In a quantum system, because of tunneling, the system can reach these lower ground states. Rather than being in a fixed position the way our magnets were, qubits are in a quantum superposition, so they can reach a lower energy state without having to climb up that energy hill. Or so we're lead to believe by the numbers, anyway; I'm not a physicist. Now, if you can map some useful computational question onto the original configuration of qubits that is answered by the ending position, you've got yourself a useful quantum computer. This is the hard part! The key is to use optimization algorithms where a lower energy state = a more optimized result. If you can do this, there's a ton of employment waiting for you. Then, if you want "quantum supremacy", it's matter of providing more optimized answers in less time, particularly as the problem scales up in complexity. There does indeed appear to be a crossover point coming in a decade or so, at least for the small class of real-world problems that the Ising Hamiltonian works for.
gtirloni 7y ago
I've read almost all comments here and, although I've grown up with lots of technology, this is the kind of stuff that will turn me into my parents/grandparents. It's like when I was teaching them how to operate the VCR years ago.
- ramraj07 7y ago
  Your analogy explains itself away - maybe you knew how everything inside a vcr worked but I didn't, I just knew what the buttons did and how to clean the head. I'm sure we will figure our way around these quantum knobs as well! (Seriously though, why the hell did those vcrs have such a large green board??)
6gvONxR4sf7o 7y ago
>Q12. Even so, there are countless examples of materials and chemical reactions that are hard to classically simulate, as well as special-purpose quantum simulators (like those of Lukin’s group at Harvard). Why don’t these already count as quantum computational supremacy? >Under some people’s definitions of “quantum computational supremacy,” they do! The key difference with Google’s effort is that they have a fully programmable device—one that you can program with an arbitrary sequence of nearest-neighbor 2-qubit gates, just by sending the appropriate signals from your classical computer. >In other words, it’s no longer open to the QC skeptics to sneer that, sure, there are quantum systems that are hard to simulate classically, but that’s just because nature is hard to simulate, and you don’t get to arbitrarily redefine whatever random chemical you find in the wild to be a “computer for simulating itself.” Under any sane definition, the superconducting devices that Google, IBM, and others are now building are indeed “computers.” This is the core of it to me. It's a question of 'some people’s definitions of "quantum computational supremacy."' Many people say that the definition here is a crappy one, and sure this shows a form of it, but not the kind to justify the hype. Sure, it's fully programmable, but not so programmable as to do anything that anyone cares about (even a teeny tiny few-bit version of something people care about) better than we can otherwise. To appeal back to his analogy to the wright brothers, it's like they carved a frisbee from a stick while working towards airplanes. It's amazing that they carved a log into a neat shape you can throw further than another log, and the hype train is saying that it's fully carve-able, so it counts as "airplane-supremacy," but that's a crappy definition and not what we're waiting for.
- whatshisface 7y ago
  At the time of the Wright brothers, which was incidentally before Frisbees were invented, there were some naysayers that thought heavier than air flight was simply impossible. A Frisbee, which can be chucked much further than a balloon, would for them serve as actual proof of "wooden supremacy."
  - 6gvONxR4sf7o 7y ago
    Interesting. Any idea how they responded to the obvious retorts about heavier than air birds?
someotherone 7y ago
So it looks like QC is good for speeding up simulations, and with far less overhead for ECC and such than it needs for things like factoring. So is simulation the QC "killer app"? Does it only do certain kinds of simulations well, i.e. simulations of quantum systems, or can that be generalized? Can it be applied to economic, environmental, traffic, etc as well?
- sanxiyn 7y ago
  There is no known useful application of current quantum computing (so-called NISQ, for Noisy Intermediate-Scale Quantum). It is an open question whether there is any, see https://arxiv.org/abs/1801.00862 https://arxiv.org/abs/1801.00862.
- OscarCunningham 7y ago
  >Can it be applied to economic, environmental, traffic, etc as well? Our current understanding is that quantum computers won't offer a speedup for the simulation of nonquantum systems. The only simulations they'll be faster for are systems for which quantum effects are important. Of course it's possible that someone will discover an algorithm that gives quantum computers an exponential speedup in the simulation of any system. But I think that's pretty unlikely because it would imply that quantum computers were exponentially faster than classical computers computers for every problem, because you could just use your quantum computer to simulate a classical one.
  - nullc 7y ago
    > Our current understanding is that quantum computers won't offer a speedup for the simulation of nonquantum systems. The speedup from grover's algorithm is essentially universal it's just not an exponential speedup. So for example in your non-quantum simulation task, you want to search for an input to a cellular automata that makes it spell your name after 5000 timestemps. You can use grover's algorithm to find that input with a sqrt() the number of simulation runs that a classical machine would need (and perhaps fewer, since there are likely multiple solutions). To me that's one of the most interesting things about quantum computation: There is a very broad class of things where it offers a modest speedup (sqrt) and a narrow (but useful!) class of things where it offers an exponential speedup. But if you imagine almost any kind of 'superpowered quantum computation'-- something that is a little more powerful than the laws of physics as we know them allow-- you almost always get an exponential speedup for everything (or even more absurd results, like every problem being solvable in constant time). QC has this interesting property of being just strictly more powerful than classical computing, but without being magic-instant-computing. [Which is also why many of the common incorrect descriptions of quantum computing are sad, stuff like "testing all values in paralle"-- if it worked like that description it would be magic instant computing.]
kwakuDompreh 7y ago
Google achieved this some few days ago and I’m very much impressed. They indicated the quantum machine could process data in 3mins and that same data will take 20years for the most advance Computer to process successfully. Impressive
nabla9 7y ago
> But others, including my good friend Gil Kalai, are on record, right here on this blog predicting that even quantum supremacy can never be achieved for fundamental reasons. I won’t let them wiggle out of it now. Here is Gil Kalai's post from yesterday: "Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google)." https://gilkalai.wordpress.com/2019/09/23/quantum-computers-amazing-progress-google-ibm-and-extraordinary-but-probably-false-supremacy-claims-google/ https://gilkalai.wordpress.com/2019/09/23/quantum-computers-...
- n4r9 7y ago
  Note also Kalai's comment on this very blog post: > Scott is correct that inability to achieve quantum supremacy is quite central to my argument (since 2014), so naturally I don’t expect that the recent claims by the Google team will stand. Of course, if these claims (or any other quantum supremacy claim) are correct then this would defeat my theory. It goes without saying that the claims are so fantastic that also responsible believers in quantum computers should examine these specific claims (like an alleged NP=! P proof) carefully and skeptically. Also, it would be nice to hear some details about the precise claims and methodology of the Google team. https://www.scottaaronson.com/blog/?p=4317#comment-1819916 https://www.scottaaronson.com/blog/?p=4317#comment-1819916
ragerino 7y ago
I recently told a friend, that the perfect quantum computer application would be a machine that can apply all possible operations simultaneously and consistently filter out one or more of the methods which results in a valid computer program producing a predefined result.
deleted 7y ago
[deleted]
tomerbd 7y ago
Can I use it for my new ruby on rails webapp?
Robotbeat 7y ago
Practically speaking, how long until the Quantum Jubilee, when (much of) encryption is broken?
amai 7y ago
It should be mentioned that IBM managed to simulate a 56 qubit version of the same problem Google describes in the paper (see https://pastebin.com/RfUMXJZE https://pastebin.com/RfUMXJZE) on a classical super computer: - https://www.ibm.com/blogs/research/2017/10/quantum-computing-barrier/ https://www.ibm.com/blogs/research/2017/10/quantum-computing... - https://www.newscientist.com/article/2151032-googles-quantum-computing-plans-threatened-by-ibm-curveball/ https://www.newscientist.com/article/2151032-googles-quantum... So technically Google cannot claim to reach quantum supremancy with only 54 qubits as described in the paper.
deleted 7y ago
[deleted]

603 points by xmmrm 7y ago

Preface: I know nothing about quantum computing. What exactly is a qubit? I'm not asking what does it mean, because I know there's superpositions and all that jazz, but as in...like, in an electronic circuit, what is a qubit? Is it made out of logic gates? Which ones? If we can make one qubit, can't we just make a bunch of them by copy and pasting circuits similar to how we used vacuum tubes in the 60s and 70s? How come our current limit is only around 54 or so? Are qubits, and quantum computers by extension, not even electronic circuits? If so...what the hell are they?

Analemma_ 7y ago
Just like a bit, a qubit is an abstract representation of information, which can be physically instantiated in different ways.
freeone3000 7y ago
You can do it with electron spin or photon polarization or by any number of properties, but it's the state of a fundamental particle. It's an entirely new type of computing apparatus, using the fundamental state of particles. No electron circuits, those won't work. And it's expensive because of the above. These things are massive, have to be kept at cyrogenic temperature, and isolation gets harder the more particles you have.
- drdeca 7y ago
  I thought a qubit could also be implemented with current going around a superconductor loop. Is that incorrect?
  - ben_w 7y ago
    You can implement them like that. Anything that has a quantum state that doesn’t decohere too fast will work. The hard part thus far has been that almost everything does decohere too fast.
  - Denvercoder9 7y ago
    No, that's indeed a quite popular approach.
rolltiide 7y ago
I'm in the same boat. A qubit can have more than the two states that a transistor can have, got it. Okay, now what can we do with that? "crack encryption by simulating a state!" yeah but what? is that something I should be concerned about now? "hahaha no no no silly normie we'd need two thousand qubits for that, this machine only has 53!" oooookay, and you did that number in your head, how??? "we just solved the first unsolvable problem that a mere bit bound supercomputer couldn't solve, look at this math formula!" but that didn't explain "we are celebrating, are you not celebrating" There just seems to be a lack of non-introductory but non-PhD level information. Where is the "explain it like I've been accepted into college at all".
- rmidthun 7y ago
  Since we're looking at Scott Aaronson, you might want to check out "Quantum Computing Since Democritus". It gives a good explanation of the math behind qubits and how they can be used. Best intro I know of.
  - rolltiide 7y ago
    thank you for that and not trying to explain it in an additional convoluted way
- rini17 7y ago
  Schrodinger's cat in unopened box is 1 qubit = it's alive and dead at the same time. When the box is opened to observe the result, the quantum state "decoheres" - decays to 1 bit result. Now imagine 53 such boxes, interconnected by quantum gates. The 53 qubits combined are in all of 2^53 states at once. The gates can be set up such that some combinations like "cat 1 alive", "cat 2 dead", etc. are much more likely result than others, after the boxes are opened. And all this computation is done in one step, whereby the classical computer must do 2^53 steps to get the same result. To have 53 cats all undisturbed in these dead/alive states so that computation is done without errors is very technically challenging :)
  - drdeca 7y ago
buboard 7y ago
for example an electron or a polarized photon. they can take the value 0 and 1 when measured but when not measured they can be in superposition states. Quantum physics forbids copying a qubit to create another, but you can initialize them en masse to to be in a superposition state. Those things are too tiny to be easily manipulated so 53 is quite an accomplishment.
- AgentME 7y ago
  >>If we can make one qubit, can't we just make a bunch of them by copy and pasting circuits similar to how we used vacuum tubes in the 60s and 70s? How come our current limit is only around 54 or so? >Quantum physics forbids copying a qubit to create another, but you can initialize them en masse to to be in a superposition state. Those things are too tiny to be easily manipulated so 53 is quite an accomplishment. Quantum physics forbids copying the value of a qubit, but the poster was asking why we couldn't just make more of the device that implements a qubit. The big issue is that you want the qubits to be entangled together and it's hard to prevent decoherence as you make a larger device with more qubits.
itcrowd 7y ago
Essentially, they use superconducting electronics to create a quantum circuit. It's not the same logic gates as a traditional computer chip and not based on the same physics. The details are difficult & messy. There are several reasons it doesn't scale easily to more qubits, but you can imagine that you don't want the chip to be large (must be cooled to 25mK!) but the qubits should be spaced quite far apart so they don't influence each other. Also, it's not a very simple circuit, so the layout of the transmission lines ("wire on a chip") becomes difficult to manage. The last problem also scales badly with the number of qubits (the middle qubit becomes progressively harder to reach). There is a paragraph in the (leaked) paper that describes their chip: > In a superconducting circuit, conduction electrons condense into a macroscopic quantum state, such that currents and voltages behave quantum mechanically [2, 30]. Our processor uses transmon qubits [6], which can be thought of as nonlinear superconducting resonators at 5 to 7 GHz. The qubit is encoded as the two lowest quantum eigenstates of the resonant circuit. Each transmon has two controls: a microwave drive to excite the qubit, and a magnetic flux control to tune the frequency. Each qubit is connected to a linear resonator used to read out the qubit state [5]. If you want a physical picture, check out [6]: https://arxiv.org/abs/cond-mat/0703002 https://arxiv.org/abs/cond-mat/0703002 edit: source [6] is more appropriate and open to access
- outworlder 7y ago
  Holy hell. > > In a superconducting circuit, conduction electrons condense into a macroscopic quantum state, such that currents and voltages behave quantum mechanically [2, 30]. Our processor uses transmon qubits [6], which can be thought of as nonlinear superconducting resonators at 5 to 7 GHz. The qubit is encoded as the two lowest quantum eigenstates of the resonant circuit. Each transmon has two controls: a microwave drive to excite the qubit, and a magnetic flux control to tune the frequency. Each qubit is connected to a linear resonator used to read out the qubit state [5]. I understand most of the words in isolation – and I know that they are valid, even if combining them in a useful manner to understand exactly what they are describing is eluding me. But if there was ever a paragraph that sounded like pure technobabble, this is it. Replace the technobabble found in the star trek matter transporter with quantum lingo, and it would sound very similar.
diegoperini 7y ago
> What exactly is a qubit? A bit is like a boolean type, has the values of true and false. Or you treat those values as 0 or 1, then gather a bunch of bits to build useful numbers. A qubit is like a pair<number, number> such that these numbers MUST satisfy the following constraints: pair.left^2 + pair.right^2 = 1 pair.left and pair.right can be any complex number Why such a composite type with weird constraints you may ask? Because that's how properties of really small particles behave in the real world. So the hope is, maybe if we can build our software using this weird data type called qubit, we can implement computation on quantum hardware without abstracting every problem using a dump type like a boolean or its aliases/collections. Remember that classical computers use a clock to flip bits over time. A similar quantum computer would manipulate qubits instead. A bit has the storage capacity of 2 distinct bits of information. A qubit has the storage capacity of 2 complex numbers, which corresponds to 4 floats, which is at least 16*8 bits of information if we are conservative about our assumptions. > Is it made out of logic gates? Kind of. Most of the current logic gates are built with semiconductors. It means by applying different voltages/currents/flux etc to different parts of a solid material, we can alter what we measure in some other part of the same material. A quantum logic gate uses the same principle but in order to achieve the desired speed and storage advantages, it uses an object with a measurable property that at least approximately behaves like a quantum mechanical object. Common semiconductors are too crowded of atoms in terms of their body parts to make good quantum materials. They touch to each other and are almost always exposed to air. Their running temperatures are undesirably high. A really dark (literally without a single photon) vacuum chamber that holds a really small amount of floating matter in the middle, frozen with lasers up to 0.000...1 Kelvin would make a good example of a stable but expensive qubit. We can measure this qubit by destroying its state, i.e by applying a magnetic field and measuring the emitted photon's location, polarization or frequency. The problem is, copy pasting this device to build a circuit is really hard due to logistics and auxiliary machinery required to keep all the state stable. > How come our current limit is only around 54 or so? That's not a fundamental limit but an engineering one, due the issues I mentioned above. The bigger the device gets, the harder to maintain its stable state. The method currently used for reaching this limit really looks like what is used in the 60s. History is repeating itself with a small twist, the running temperature is extremely low this time. Not liquid nitrogen low, but compressing atoms by sniping them from distance via laser on multiple directions low. There is also one more problem that is unique to quantum computers. You have to measure the same qubit multiple times to be able to read those complex numbers since their values are determined statistically. You either represent a qubit with multiple qubit like devices or you use the same device to try your measurement repeatedly. Each approach comes with its own drawbacks. > Are qubits, and quantum computers by extension, not even electronic circuits? Even today, non quantum circuits are sometimes non electronic in some of their parts. Fiber optics, supersonic emitters/receivers and photoelectric sensors are good examples. To this day, it is not clear whether the first consumer quantum CPU will be entirely electronic or not.
raincom 7y ago
"[T]hose believing that a QC can manipulate or maintain huge objects "free of cost" (i.e., at unit cost) should provide a convincing explanation to this fantastic speculation. Being skeptic of this (rather over-simplified and counter-intuitive) speculation seems to be the default and natural position." (From http://www.wisdom.weizmann.ac.il/~oded/on-qc.html http://www.wisdom.weizmann.ac.il/~oded/on-qc.html )
3PS 7y ago
Short answer, a qubit is a unit vector in a 2D complex Hilbert space. Now, that doesn't actually say much about why we care or how they're useful. In practical terms, you can think of qubits as complex unit vectors along two axes, with one axis corresponding to |0⟩ (the zero qubit) and one axis corresponding to |1⟩, or the one qubit. So for example, you could have a qubit called |+⟩, which is just shorthand for (|0⟩ + |1⟩)/sqrt(2). Measuring a qubit in a basis collapses it to one of the basis vectors (e.g Schrödinger's cat must be alive or dead once we open the box) with probability equal to its inner product with that basis vector. This is why we need a Hilbert space and not just any old vector space. Finally, to answer your question about gates, a quantum gate is basically a unitary matrix, i.e. a matrix that preserves the norm of its inputs. You can feed qubits into these matrices by themselves or, more often, many at once, by using something called the tensor product of the qubits - this is where the math gets slightly more involved. The long and short of it is that we can induce correlation patterns between qubits using these gates (aka quantum entanglement) and orchestrate circuits of interference patterns where the wrong answers cancel each other out and the right answer gets reinforced so that we measure it at the end - unfortunately, this is where my knowledge breaks down as a beginner. My apologies if I accidentally handwaved anything important but hopefully you get the gist.
- galaxyLogic 7y ago
  > Schrödinger's cat must be alive or dead once we open the box I recently had a conversation about this in another thread. It seems to me, and nobody tried to convince me otherwise, that the Cat would be the Observer. Therefore it would be dead, NOT dead AND alive, as soon as it observes the poisonous gas in its box.
  - 3PS 7y ago
    So this is a little nuanced. It's true that quantum systems collapse on "observation", but that doesn't actually mean "observation by a sentient entity". It could really just be any interaction with the outside environment. (This is why qubits have to be kept incredibly well-isolated.) We don't really fully know exactly how this collapse works, and related speculation is generally classified under the measurement problem [1]. But it's true that one of the key points of Schrödinger when proposing his thought experiment was that the notion of measurement or observation was not fully defined under the Copenhagen interpretation. Side note, it's not that the cat is observing poisonous gas, but rather, that a Geiger counter is set to detect whether a radioactive atom decays or not and triggers the release of some poisonous gas if so. So, classically, Schrödinger's cat would be either alive or dead 50% of the time, not 100% dead. There are plenty of alternative ways to reconcile this classical view with quantum mechanics. Perhaps the simplest and most well-known is the many-worlds interpretation [2], which states that both events occur, just in different timelines, and we don't know what timeline we ended up in until we open the box. (Of course, it is ridiculous to speculate as to which timeline "we" end up in before the experiment is carried out, because the people in both timelines would still be "us" - this can get awkward to think about.) [1] https://en.wikipedia.org/wiki/Measurement_problem https://en.wikipedia.org/wiki/Measurement_problem [2] https://en.wikipedia.org/wiki/Many-worlds_interpretation https://en.wikipedia.org/wiki/Many-worlds_interpretation
cdumler 7y ago
TL;DR: A quantum computer is a device that uses the measurement of quantum properties to do computation. There are many ways to implement one depending on the type of entangled particles being used, from crystals to make entangled photons and superconducting mounds to entangle electrons. This is the same for binary computers, which can made from electrical devices (transistors), values with air pressure or balls falling down wooden ramps. Longer version An observation about quantum behavior is that there are only certain properties that you can measure for the really, really small. These include things like mass (total energy), charge (intrinsic amount of electromagnetic strength), and spin (willingness to change direction in the presence of an electromagnetic field). It turns out that when you measure these properties, the measurements behave in non-intuitive ways. The act of measuring the spin of a particle (which could be in any direction) is really the act of asking, "is this particle aligned with my detector?" The result will always be either aligned up or aligned down. It will be randomly about 50/50 up and down, also. This is not that surprising because the spin must align one direction or the other. The crazy part comes with the fact that you can entangle two particles. Entangle particles can be sent off through different detectors and one thing will always be true: while any particular outcome is random, the detectors will always generated opposite results. The temptation is to say, "well, they were generated from the same source, so they have just opposite starting positions." Long story short, this has been proven not possible. Instead, there is some fundamental behavior is quantum mechanics that says that there are certain types of activities with entangles particles that have a correlation that is true as long as the entangle particles are not disrupted. In this case, particles sent to separate detectors will always have opposite results. A quantum computer uses these correlation truths about measurements to do computations. A qubit is the concept of a quantum bit: an entity that represents one unit of entanglement. Just like a bit, quantum computers have many different ways to implement entanglement. You can entangle photons, electrons, and whole atoms. Each of these systems require specific implementations to achieve, like like electronic or mechanical computers. Remember that one detail about "if they are not disrupted?" Yeah, turns out that it takes a hell of a lot to create an environment that doesn't destroy the coherence of the entanglement. You have to design something that allows you to setup the particles into starting state, be able to hold those particles in an entangled state with no disruptions and have a detector to determine the final state. Quantum mechanically, these are generally opposite goals.
tagrun 7y ago
Physicists here. In practice, a qubit is a two-level physical system. It can be spin state of an electron, polarization of a photon, lowest two energy states of an atom or an electron in quantum dot/well trap potential, the charge state (called charge qubit) -- whether you have 0 or 1 electrons in it, etc etc (if you have 3 levels, it's called qutrit, and for d levels qudit). This experiment uses charge qubits (a special variant which has some robustness against charge noise by design [by operating at a voltage level which is insensitive to 1st order fluctuations in the electric field, called "sweet spot"], called transmon). The main problem is achieving full control of these systems, which is extremely hard, because there are certain things (some random/stochastic) that you can't control at all and you have to fight+race against their influence: - qubits are tiny, and the energy splitting between these two states are typically minuscule: this means even a small vibration from a sneeze miles away can make the qubit flip. - qubits do not live in vacuum, they are typically hosted in solid-state systems and the qubits are coupled to their hosting environment, which have their own moving parts (two-level fluctuators which lead to charge noise, phonons which also couple to electrons typically via spin-orbit coupling, spinful defects in the material which have their own dynamics, etc etc) that you can't really control. it's extremely difficult to achieve full control of a qubit in the presence of things that you can't control and random in nature. - if the qubit is the lowest two-levels of a system with higher energy levels, one also needs to worry leakage errors to those higher states - there are ways of suppressing the influence of such unwanted interactions (dynamically corrected gates + quantum error correction codes) given that their strength is below certain thresholds. going below those thresholds is again an enormous engineering/material science problem (extremely low temperatures, isolation from vibrations, low/high-pass filters for the classical circuitry which is used to control/drive the qubits via electric/magnetic fields, design of the device itself which typically hosts two-level fluctuators, etc etc). this problem becomes harder in general as you increase the number of qubits though. - to do anything non-trivial, you need to have more than one-qubit and have controllable couplings between those (so you can't put them apart too far which makes it impossible to couple them). this doesn't work perfectly in practice, you can't completely control or turn off their couplings (a problem called cross-talk) which again leads to errors. so it doesn't work quite like modular classical circuit elements which you can "copy & paste" because the abstractions from the low-level, nitty-gritty physics of the underlying material fail for all these qubits.
justinpombrio 7y ago
> If we can make one qubit, can't we just make a bunch of them by copy and pasting circuits similar to how we used vacuum tubes in the 60s and 70s? How come our current limit is only around 54 or so? This is a very good question! And as far as I can tell, no one has actually answered it yet. In classical physics, which suffices to explain circuits made of vacuum tubes, the state of a system is fully captured by the states of its parts. Like, if you want to know the state of three bits, I just have to tell you what the first bit is (0 or 1), and the second bit, and the third one. Basically everything we interact with has this property: if you fully describe the state of each part of a thing, you have described the state of the whole thing. But quantum mechanics is... weirder than this. In quantum mechanics, to describe the state of a system you have to give one complex number per classical state, such that the sum of the squares of the absolute values of the complex numbers adds up to 1. These complex numbers roughly correspond to the "probability" that the system is in that state (but not quite, it's more complicated than that). So in quantum mechanics, to describe the state of three bits, you have to give eight complex numbers n1,n2,...,n8, one for each of the classical states of the bits 000, 001, 010, 011, 100, 101, 110, 111, where the sum of the squares of the absolutely values of n1,...,n8 add up to 1. That's a lot more information than 3 bits. (Imaging if you had 54 bits... you'd need 2^54 ~= 10^17 complex numbers to describe them.) Technically, everything in the whole world, including you, is described by the laws of quantum mechanics. So why don't we see weird quantum effects all of the time? Quantum systems are very fragile: whenever they interact with the outside world (say a photon from the air bounces off of something in the system), the system "collapses", and then behaves as classical physics would predict. (Note that this is in accordance with the quantum prediction. The system goes from "only describable using difficult quantum mechanics" to "describable using quantum mechanics, but it'll just say the same thing as classical physics, and classical physics is simpler so you should just use that".) So here's what a qbit is: it's just a regular bit that has been so insulated from the outside world that classical physics doesn't suffice to describe it. You won't find qbits on a regular circuit board, though, because they'll interact with the circuit board in any way whatsoever and then you're done. And this is why making a 54-qbit quantum computer is so hard. You need to keep all of the qbits isolated, because if any of them interact with the outside world (think the air in the room, or a single photon, or the substrate that the qbits are on), then the whole system "collapses".
grumpy8 7y ago
Extremely simplified: >> in an electronic circuit, what is a qubit? It's not an electronic circuit, it literally is an electron or a photon. And it's using that particle's properties to do "superposition and all that jazz". You can't put too many next to each others because they start interacting together because that's what electrons do when they get close.
- deleted 7y ago
  [deleted]
tzs 7y ago
> If we can make one qubit, can't we just make a bunch of them by copy and pasting circuits similar to how we used vacuum tubes in the 60s and 70s? How come our current limit is only around 54 or so? (I'm not an expert in this area, so the following may not be incomplete or limited to only certain kinds of quantum computation, or worse). The kinds of computation that qubits can beat a classical computer on require that the qubits be entangled. If the qubits are not entangled, you can't do better than regular bits. Briefly, if two (or more) quantum systems are entangled, and you make certain measurements that have a random outcome on one of the systems, and then measure the same property on the other system(s), there will be correlations that you would not get if the systems were not entangled. The entangled systems act is if whenever you measure one and it randomly chooses a value for the property you measured, that result is somehow communicated to the other entangled systems, and they make sure them that when they are measured they will give results with the appropriate correlation. You might think that this could be explained if the systems had some internal variables that were set when they became entangled that determined what "random" values they would pick when later measured, but there are experiments that have shown that this is not so. The systems are truly making their random choice at the time of measurement as far as we can determine. This happens even if after you entangled the systems, you separate them by a great distance--so far that between the time you do the measurements on the separate systems there is no time for any communication between the systems (or, rather, no time for any communication limited by the speed of light--I believe there have been experiments showing that IF there is communication, it is at more than 10000 times the speed of light). (This communication, or whatever it is, cannot be used to send messages faster than light. All it can do is make the correlations work out for entangled systems). Anyway, the thing about entangled systems is that as soon as you make a measurement of the entangled property, you lose the entanglement. Your particle that had entangled spin, say, with another particle and that was 50/50 whether it was spin up or spin down becomes, once you actually measure spin, a non-entangled particle whose spin is a concrete value, either up or down. Measure it again, and you get the same value. When I say "you make a measurement", I don't specifically mean you, or any other human, or any human instruments. For purposes of quantum mechanics, a measurement is anything that makes the system reveal a value. So if you have a particle with entangled spin with some other particle, and some random passing particle happens to interact with yours in a way that depends on the spin of your particle--that's a measurement and you've lost your entanglement. (Your particle might now be entangled with that random passing particle, but it is no longer entangled with the particle you intended it to be entangled with). If you are trying to do a quantum computation on 50 qubits, you have to get them all entangled, and then you have to keep them from interacting with anything that might inadvertently do a measurements long enough for them to do their quantum computation, where you can then measure the result (which finally ends the entanglement). This turns out to be hard, because there are a lot of things in the universe that want to effectively do a measurement. Any random particle bumping into one of yours with too much energy can do it. Some random passing electromagnetic wave can do it. The more things you need to entangled and keep entangled, the hard this is, and 50ish is the current limit.
sundarurfriend 7y ago
Quantum computing for the very curious [1] has been very useful to me, for getting at least a basic idea as to what exactly a quantum computer is, what a qubit is, and how they are manipulated. [1] https://quantum.country/qcvc https://quantum.country/qcvc

ClintEhrlich 7y ago

I've been waiting for Scott Aaronson to put all of this into perspective since the first leaks about Google's quantum supremacy started appearing in popular media. He has exceeded my expectations with this post, which cuts through all the hype to communicate exactly what the results of this experiment mean for the field. It's worth reading and sharing.

ClintEhrlich 7y ago
On second reading, I have but one trivial gripe: "Enormity" implies moral reprobation, so it's a poor way of describing the significance of a computational discovery.
- klipt 7y ago
  Isn't it just Enormous : enormity :: huge : hugeness?
  - ClintEhrlich 7y ago
    Not quite. Enormous : enormousness :: huge : hugeness. Enormity = Immense scale of evil (e.g., the "enormity of the holocaust")
    - alanbernstein 7y ago
      Thanks for the enlightening nitpick, this is one of those terrible/terrific things about English that I love/hate.
    - andrewflnr 7y ago
      As a native English speaker, I can't say I've found this to be the case. "Enormity" does tend to be used for dramatic effect, most often on moral issues, but I don't think that makes Scott wrong to use it here. I don't know if I've seen "enormousness" before this thread.
      - 7y ago

whatshisface 7y ago

If it goes well, the history of quantum computing will be divided up in to three eras: the era of twisty philosophical arguments that it's working ("the molecule is simulating itself"), the era of academic arguments that it's working ("we can solve this one carefully constructed problem") and the era of practical arguments ("Amazon is selling QC time for $20/kilogate-bit, what do you mean it's not possible?"). Quantum supremacy marks the transition from the first era to the second.

p1necone 7y ago
I really enjoy seeing comments on here that fit the 3rd kind. "Thing is ridiculous, that could never work because of reasons A, B and C." "What are you talking about, here is project that does thing, it functions perfectly." Nothing like reality proving someones baseless naysaying wrong immediately.
- smsm42 7y ago
  Except reality has so far proved that it is possible to use QC for solving one QC-specific task that is hard to solve classically, that's it. That's not what "naysaing" was about - the "naysaying" was about the fact we have no way to use QC for known classical tasks, and the path to such juicy targets as breaking commercial public key encryption is entirely unclear. Virtually nobody says it would never ever happen - but so far it has not happened and will not happen soon, and reality has not proven anything contradicting that yet. When, in 2038 or in 2083, the reality finally gets there, then your condescending attitude towards the naysayers would finally be completely warranted. But not yet.
gowld 7y ago
What are the theoretical models for the energy cost of computing on a qubit? I'll be excited for QC when there is known way (even with some handwaving and future-tech plans) to compute a non-trivial result for a reasonable sum, such as "crack someone's private RSA key for under $10M of compute cost"
- sanxiyn 7y ago

19ylram49 7y ago

Much needed perspective in the age of overly dramatic headlines and straight up misinformation.

age_bronze 7y ago

I posted this on scott's blog, still awaiting moderation: "I’m trying to understand the chain of inference from Google’s leaked result of quantum supremacy to theoretical computer-science “hardness” of the computation. Computing the exact probabilities of a random quantum circuit is proven hard, but computing the exact probability of a random algorithm is also an open problem, so what you really care about is approximation of computing the probability (up to epsilon), or even weaker, just sampling from a probability (also up to epsilon under some metric of comparing distributions). Their computer implements Random Circuit Sampling, and their cited “theoretical” hardness results are your paper from 2017, of QUATH => HOG, and as far as I understood from your paper, proving that approximation / sampling from a (random) quantum computer/circuit is hard is still an open problem (Am I wrong here? I’m not up to date with everything), and a difficult one. But you did make a compelling argument that even if QUATH was solvable, it will lead to new insights. Their actual benchmark uses cross-entropy benchmarking, called xeb in their paper, and defined as 2^n* [P(x_i)] _i-1 (Can’t type brackets). I could not find any ‘theoretical hardness’ paper at all using this benchmark, some results talk about different XEB using log but they prove these are not strong enough and can be reached classically. Are there any hardness results for their benchmark? I wonder why they would use that instead of the proven HOG, even for smaller input sizes, I would see more value in a benchmark which has theoretical roots. I feel intuitively like their benchmark is much more similar to the log variation of XEB than to HOG, but didn’t think it through completely. As for their gates, I understand they are not general random quantum gates, but instead they have a variation of iSWAP and controlled phase CZ. The hardness results that do exist also don’t address the limited gates, in how it changes the distribution of random circuits. Are those two gates at least universal, so that we have hope that this could be proved? Their statement was “but reliably generating a target unitary remains an active area of research”, so I assume they aren’t universal. I would love to see some heuristic argument as to why those two in particular are hard, especially given results like Gottesman–Knill theorem, it seems like some surprising gates do have classical simulation. iSWAP is just swap and phase gates, and CZ is phase gate only on the 11 state. Doesn’t feel like it could be universal to me but maybe I’m wrong. I probably missed some things, so I’d love it if you could point to papers filling the gaps between their results and a real theoretical statement. I don’t have the intuition to tell which gaps are important and which are not. I also don’t know which papers/results already exist and I can’t really search as I am not an academic, and don’t have full access to many papers, and you probably know the state of the art results. "

codeulike 7y ago

My cat can behave as a cat would be expected to behave. And if we verify the measurements of her behaviour using a classical computing cluster - to make sure her behaviour really falls within the distribution of expected cat behaviour - thats a very complicated calculation that will take many processor-days. But my cat can just do that stuff in real time. Has my cat achieved Quantum Supremacy, and is there a trophy or something I can pick up somewhere for that?

teraflop 7y ago
That sounds like question 12 from the FAQ ;)
- codeulike 7y ago
  Ah yes, indeed. So it hinges on whether my cat is programmable. Well as it happens my cat has a number N of programmable modes: 1 - cat having its ears tickled 2 - cat watching something move under a sheet that might be a mouse 3 - cat waiting for tin of cat food to be opened 4 - cat wanting to get through a door etc etc up to 'N' So a “challenger” generates a random number C between 1 and N, and the challenger then sends C to me and my cat, and I apply the appropriate 'input' to my cat, tickling her ears or openeing a tin of food or whatever, to get her into the correct mode. We then measure her behaviour and then fire up our cluster of computers and run the simulation and then wait for a few months for the numbers to get crunched to verify if the cats behaviour was within expected probability distribution for C.
  - SpicyLemonZest 7y ago
    "Programmable" in this context would mean that you can encode complex computational problems into your cat's behavior. The idea is to distinguish a cat that can only calculate cat behavior (which is of course a very easy problem) from a cat that could eventually be engineered to calculate whatever you want. If you can solve complex computational problems faster than a cat-sized computer by carefully arranging tins of cat food, it would definitely be fair to say your cat computational supremacy is a significant achievement.

westurner 7y ago

Who even asked these questions? I question this. All of this.

fastball 7y ago
Literally people on HN have been asking many of these questions for years whenever QC is discussed.
- westurner 7y ago
  I believe Feynman originally asked the QC question many many years ago. What an exciting milestone and a great FAQ. "Always naysaying! Everything I create!"

bjornsing 7y ago

I have the greatest respect for Scott, but I do think he’s being a bit too enthusiastic here in comparison with the D-wave. At the very least I think he should have included this question in his list: Q: Why can the D-wave not be used to illustrate “quantum supremacy” in a similar way? (As I understand it the D-wave can sample from the solutions to ”ising model-like” problems, which I assume would be extremely difficult for a classical computer to do (but probably possible to verify).)

rsln-s 7y ago
Unfortunately, the same complexity considerations do not hold for Ising problems. While many NP-hard problems can be formulated in Ising form, it is often not hard to get a “pretty good” solutions to these problems. DWave and collaborators have spent a decade trying to come up with exactly the same thing as demonstrated here — namely, a problem specifically designed to demonstrate quantum advantage of any sort — and as of now did not succeed. To answer your question specifically: DWave does not allow the same level of control over qubits.
- bjornsing 7y ago
  I’m aware of D-wave’s struggles, but my impression was that they had failed at finding a “deterministic” problem where they could show quantum advantage. I’ve never heard a claim that whatever probability distribution the D-wave can sample from a classical computer can also sample from. I’d love to read about it if you have a reference!
  - sanxiyn 7y ago
    My understanding is that it is exactly the case D-wave probability distributions can be sampled classically.
bjornsing 7y ago
Another reason I feel this is oversold: This quantum “computer” cannot run Shores factorization algorithm. But if it could it would only be able to factor integers up to 2^53. The time required to factor a 2^60 to 2^80 integer on a classical computer is measured in milliseconds [1]... Quantum supremacy in any reasonable sense of the word supremacy is a long way off. 1. https://hal.inria.fr/file/index/docid/451604/filename/smallint_expcomp_draft_02_1.pdf https://hal.inria.fr/file/index/docid/451604/filename/smalli...

calhoun137 7y ago

I think we need to comes to grips with a hard truth about the reality of academic life. Once you invest decades of your life into a research subject, if it turns out the entire thing is never going to work, there are major social and financial pressures to deceive the public about the true nature of the subject. I saw this happen with string theory first hand, and my experience with string theory was a major factor that led to changing paths to pure mathematics and computer science. As someone who has spent a lot of time researching QC, I do not believe it will ever be possible to build a practical quantum computer. We have been over this so many times on this site. Here is a good link from a serious professional who takes the same position [1] In fact, my personal opinion is that quantum computers are functionally, a hoax, the main purpose of which is to generate hype, secure research grants, ensure career stability for academics, and give science reporters something to write about to get clicks while deceiving the public. [1] https://www.quantamagazine.org/gil-kalais-argument-against-quantum-computers-20180207/ https://www.quantamagazine.org/gil-kalais-argument-against-q...

dcposch 7y ago
> Once you invest decades of your life into a research subject, if it turns out the entire thing is never going to work, there are major social and financial pressures to deceive the public about the true nature of the subject. You're implying that Scott Aaronson is being deceptive. I think that needs better evidence. The story you linked to is two years old and it's about QC skeptic Gil Kalai. Scott addresses him directly in his post: > If quantum supremacy was achieved, what would it mean for the QC skeptics? > I wouldn’t want to be them right now! They could of course retreat to the position that of course quantum supremacy is possible (who ever claimed that it wasn’t??), that the real issue has always been quantum error-correction. And indeed, some of them have consistently maintained that position all along. But others, including my good friend Gil Kalai, are on record, right here on this blog predicting that even quantum supremacy can never be achieved for fundamental reasons. I won’t let them wiggle out of it now.
- calhoun137 7y ago
  I am not very familiar with Scott Aaronson and am just making a general observation about the subject of QC, I have no idea what his motivations or intentions are. If Scott believes QC will day be practical and I don't, only time can tell who is right and who is wrong. I have seen this kind of goal post moving in string theory, and its been going on for 20 years with QC in a strikingly similar way imo. There is no way to argue against this kind of goal post moving style of debate because even if another 20 years go by and QC still don't exist on a practical level, the goal posts will just keep getting moved. I am extremely confident that this will continue until the public gets bored of hearing about it.

daxfohl 7y ago

What's e.g. China and Russia doing in this space? Or the US Gov't for that matter? I can't imagine that national governments are just waiting for Google and IBM to do the research and publish their results. Is it possible/likely that NSA or some other national equivalent is way beyond these results already?

reilly3000 7y ago
I don't know what the NSA spends on R&D, but I have to imagine they don't have a multi-billion dollar budget for secret R&D facilities and talent. It would seem more likely they are monitoring developments in public and private research and responding opportunistically. I'm just making assumptions here, but also I don't think somebody with clearance could correct me here in public :P
- daxfohl 7y ago
  I'd think the opposite. I would imagine they have orders of magnitude more to spend on crypto research than a private search engine company (which is why I asked the question originally). But really I have no idea. (If they did then why aren't there job ads etc). And you're right, probably nobody who does have an idea would be able to say.
- jessriedel 7y ago
  The NSA has the money and a history of massive secret projects. There are more mathematicians at the NSA than in all of academic cryptography. However, my general impression is that most people don't think the NSA has a secret QC project because there hasn't been a noticeable disappearance of the best young experimental QC researchers from the pipeline like there has been for cryptography. It's the promising people quietly leaving that is hard to hide; massive construction projects are comparatively much easier to hide.
  - muraiki 7y ago
    A recent NYT opinion piece from the general counsel of the NSA discusses many of these issues, including quantum computing: https://www.nytimes.com/2019/09/10/opinion/nsa-privacy.html https://www.nytimes.com/2019/09/10/opinion/nsa-privacy.html

billions 7y ago

Most things that get years of speculation and press never come to fruition

smolder 7y ago
Like flying machines, speculated about from DaVincis time?

yters 7y ago

Most major breakthroughs were pretty low tech in origin, and the high tech was all about optimizing the idea. I think we get fundamental research backwards nowadays.

khawkins 7y ago
At the very least, we shouldn't be comparing quantum computing to air flight. The Wright brothers were basically hobbyists, incomparable to the global leading technology corporations in the history of human civilization. This seems more comparable to the moon landing or LHC Higgs-Boson discovery. Challenging to pull off once, and the next steps seem to increase exponentially in man-power and cost.
- scottlocklin 7y ago
  I think the proper analogy is controlled nuclear fusion, which google is also dabbling with.
- yters 7y ago
  Those haven't really brought us much benefit. The benefit to effort relationship seems to be inverse.

person_of_color 7y ago

Where does this put Rigetti Computing?

erichocean 7y ago

> It’s like, if you believed that useful air travel was fundamentally impossible Uh, there are birds. Literally everyone thought useful air travel was possible, and not only possible, but so easy that a Darwinian process was able to produce it, not once, but literally thousands of times, in thousands of ways. ---- But looking at the actual "experiment", I don't count that as computation in any meaningful sense, and morally equivalent to the following: Set up a digital camera and point it at a scene. Take a picture. Now take millions of additional pictures, without moving the camera. Measure the values at each pixel. See how they correspond to "amplitudes"? That's our computation. <= (This is the part of the article that should raise eyebrows...) Article (smugly): How about you simulate (render) the scene using an actual computer? Measure the amplitudes of the resulting millions of images. OMG, that took you so long!!! Loser. Are we being punk'd here? The digital camera is the quantum computer. The "scene" is the random initial state C. The scene is then translated into a renderable scene for the classical computing version, and rendered with an unbiased physically based renderer, which produces the same result. I fail to see how any of this is even remotely exciting, much less interesting. A camera is not a computer, no matter how many measurements you make with it, nor how "random" the scene you are taking pictures of is. And yes, simulating reality takes more cycles than just measuring whatever happened with a camera. Photos are "faster" to get than the equivalently rendered scene—news at 11! Again: Are we being punk'd here?

core-questions 7y ago
Perhaps it will make more sense to explain how a D-Wave machine works, as (a) they actually exist and you can use one today for free online, and (b) it's way simpler than a gate model QC is. Imagine a bunch of magnets. Imagine forcing them into a "frustrated" configuration; maybe you have them all on a grid, and you have servomotors that can rotate them to face any way you like. The servomotors are strong, so counteracting the magnetic forces is easy for them. You design an appropriately frustrated configuration, and then release all of the magnets at once. What configuration do they rotate into? A quantum annealer is conceptually similar. Each qubit, on a regular, patterned graph, has connections to its neighbours. You can leave these alone (no corellation) or tune them up to +/- 1, corresponding to "must be the same as this other qubit" and "must be different than this other qubit". You can also bias each individual qubit to be a 0 or a 1. Then, you let it go, and it anneals, and you observe the result. Your goal is to get to the _lowest energy state_ possible: the least possible frustration remaining. In our magnet example, it would be as few magnets as possible wanting to move - if you poked them with your finger they'd want to go back into their current state. You could imagine that your magnets might not get down to their absolute lowest energy state; maybe it would take too much energy to flip from their starting state to that lower state. In a quantum system, because of tunneling, the system can reach these lower ground states. Rather than being in a fixed position the way our magnets were, qubits are in a quantum superposition, so they can reach a lower energy state without having to climb up that energy hill. Or so we're lead to believe by the numbers, anyway; I'm not a physicist. Now, if you can map some useful computational question onto the original configuration of qubits that is answered by the ending position, you've got yourself a useful quantum computer. This is the hard part! The key is to use optimization algorithms where a lower energy state = a more optimized result. If you can do this, there's a ton of employment waiting for you. Then, if you want "quantum supremacy", it's matter of providing more optimized answers in less time, particularly as the problem scales up in complexity. There does indeed appear to be a crossover point coming in a decade or so, at least for the small class of real-world problems that the Ising Hamiltonian works for.

gtirloni 7y ago

I've read almost all comments here and, although I've grown up with lots of technology, this is the kind of stuff that will turn me into my parents/grandparents. It's like when I was teaching them how to operate the VCR years ago.

ramraj07 7y ago
Your analogy explains itself away - maybe you knew how everything inside a vcr worked but I didn't, I just knew what the buttons did and how to clean the head. I'm sure we will figure our way around these quantum knobs as well! (Seriously though, why the hell did those vcrs have such a large green board??)

6gvONxR4sf7o 7y ago

>Q12. Even so, there are countless examples of materials and chemical reactions that are hard to classically simulate, as well as special-purpose quantum simulators (like those of Lukin’s group at Harvard). Why don’t these already count as quantum computational supremacy? >Under some people’s definitions of “quantum computational supremacy,” they do! The key difference with Google’s effort is that they have a fully programmable device—one that you can program with an arbitrary sequence of nearest-neighbor 2-qubit gates, just by sending the appropriate signals from your classical computer. >In other words, it’s no longer open to the QC skeptics to sneer that, sure, there are quantum systems that are hard to simulate classically, but that’s just because nature is hard to simulate, and you don’t get to arbitrarily redefine whatever random chemical you find in the wild to be a “computer for simulating itself.” Under any sane definition, the superconducting devices that Google, IBM, and others are now building are indeed “computers.” This is the core of it to me. It's a question of 'some people’s definitions of "quantum computational supremacy."' Many people say that the definition here is a crappy one, and sure this shows a form of it, but not the kind to justify the hype. Sure, it's fully programmable, but not so programmable as to do anything that anyone cares about (even a teeny tiny few-bit version of something people care about) better than we can otherwise. To appeal back to his analogy to the wright brothers, it's like they carved a frisbee from a stick while working towards airplanes. It's amazing that they carved a log into a neat shape you can throw further than another log, and the hype train is saying that it's fully carve-able, so it counts as "airplane-supremacy," but that's a crappy definition and not what we're waiting for.

whatshisface 7y ago
At the time of the Wright brothers, which was incidentally before Frisbees were invented, there were some naysayers that thought heavier than air flight was simply impossible. A Frisbee, which can be chucked much further than a balloon, would for them serve as actual proof of "wooden supremacy."
- 6gvONxR4sf7o 7y ago
  Interesting. Any idea how they responded to the obvious retorts about heavier than air birds?

someotherone 7y ago

So it looks like QC is good for speeding up simulations, and with far less overhead for ECC and such than it needs for things like factoring. So is simulation the QC "killer app"? Does it only do certain kinds of simulations well, i.e. simulations of quantum systems, or can that be generalized? Can it be applied to economic, environmental, traffic, etc as well?

sanxiyn 7y ago
There is no known useful application of current quantum computing (so-called NISQ, for Noisy Intermediate-Scale Quantum). It is an open question whether there is any, see https://arxiv.org/abs/1801.00862 https://arxiv.org/abs/1801.00862.
OscarCunningham 7y ago
>Can it be applied to economic, environmental, traffic, etc as well? Our current understanding is that quantum computers won't offer a speedup for the simulation of nonquantum systems. The only simulations they'll be faster for are systems for which quantum effects are important. Of course it's possible that someone will discover an algorithm that gives quantum computers an exponential speedup in the simulation of any system. But I think that's pretty unlikely because it would imply that quantum computers were exponentially faster than classical computers computers for every problem, because you could just use your quantum computer to simulate a classical one.
- nullc 7y ago
  > Our current understanding is that quantum computers won't offer a speedup for the simulation of nonquantum systems. The speedup from grover's algorithm is essentially universal it's just not an exponential speedup. So for example in your non-quantum simulation task, you want to search for an input to a cellular automata that makes it spell your name after 5000 timestemps. You can use grover's algorithm to find that input with a sqrt() the number of simulation runs that a classical machine would need (and perhaps fewer, since there are likely multiple solutions). To me that's one of the most interesting things about quantum computation: There is a very broad class of things where it offers a modest speedup (sqrt) and a narrow (but useful!) class of things where it offers an exponential speedup. But if you imagine almost any kind of 'superpowered quantum computation'-- something that is a little more powerful than the laws of physics as we know them allow-- you almost always get an exponential speedup for everything (or even more absurd results, like every problem being solvable in constant time). QC has this interesting property of being just strictly more powerful than classical computing, but without being magic-instant-computing. [Which is also why many of the common incorrect descriptions of quantum computing are sad, stuff like "testing all values in paralle"-- if it worked like that description it would be magic instant computing.]

kwakuDompreh 7y ago

Google achieved this some few days ago and I’m very much impressed. They indicated the quantum machine could process data in 3mins and that same data will take 20years for the most advance Computer to process successfully. Impressive

nabla9 7y ago

> But others, including my good friend Gil Kalai, are on record, right here on this blog predicting that even quantum supremacy can never be achieved for fundamental reasons. I won’t let them wiggle out of it now. Here is Gil Kalai's post from yesterday: "Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google)." https://gilkalai.wordpress.com/2019/09/23/quantum-computers-amazing-progress-google-ibm-and-extraordinary-but-probably-false-supremacy-claims-google/ https://gilkalai.wordpress.com/2019/09/23/quantum-computers-...

n4r9 7y ago
Note also Kalai's comment on this very blog post: > Scott is correct that inability to achieve quantum supremacy is quite central to my argument (since 2014), so naturally I don’t expect that the recent claims by the Google team will stand. Of course, if these claims (or any other quantum supremacy claim) are correct then this would defeat my theory. It goes without saying that the claims are so fantastic that also responsible believers in quantum computers should examine these specific claims (like an alleged NP=! P proof) carefully and skeptically. Also, it would be nice to hear some details about the precise claims and methodology of the Google team. https://www.scottaaronson.com/blog/?p=4317#comment-1819916 https://www.scottaaronson.com/blog/?p=4317#comment-1819916

ragerino 7y ago

I recently told a friend, that the perfect quantum computer application would be a machine that can apply all possible operations simultaneously and consistently filter out one or more of the methods which results in a valid computer program producing a predefined result.

deleted 7y ago

[deleted]

tomerbd 7y ago

Can I use it for my new ruby on rails webapp?

Robotbeat 7y ago

Practically speaking, how long until the Quantum Jubilee, when (much of) encryption is broken?

amai 7y ago

It should be mentioned that IBM managed to simulate a 56 qubit version of the same problem Google describes in the paper (see https://pastebin.com/RfUMXJZE https://pastebin.com/RfUMXJZE) on a classical super computer: - https://www.ibm.com/blogs/research/2017/10/quantum-computing-barrier/ https://www.ibm.com/blogs/research/2017/10/quantum-computing... - https://www.newscientist.com/article/2151032-googles-quantum-computing-plans-threatened-by-ibm-curveball/ https://www.newscientist.com/article/2151032-googles-quantum... So technically Google cannot claim to reach quantum supremancy with only 54 qubits as described in the paper.

deleted 7y ago

[deleted]