6 ms·

I don't understand nearly enough of this stuff, but this section sounds... weird: Each run of a random quantum circuit on a quantum computer produces a bitstri

by OskarS 7y ago

I don't understand nearly enough of this stuff, but this section sounds... weird: Each run of a random quantum circuit on a quantum computer produces a bitstring, for example 0000101. Owing to quantum interference, some bitstrings are much more likely to occur than others when we repeat the experiment many times. However, finding the most likely bitstrings for a random quantum circuit on a classical computer becomes exponentially more difficult as the number of qubits (width) and number of gate cycles (depth) grow. It sounds like they're saying "simulating this physical process accurately is extremely computationally expensive, but just running the physical process in the real world is MUCH faster". But that's true of basically any physical process! Simulating turning on a single lamp in a room and figuring out how much light falls on what walls is an enormously computationally expensive process, which can take immense amount of time to figure out (depending on your desired level of accuracy). Movie studios, CG artists and game companies build entire render farms to solve this problem. But the physical process itself (just turning on the light) happens instantly. Just replace "turning on the light" with "running a quantum circuit".

goldenkey 7y ago
Pretty much. Which is why it is beyond silly we aren't using DNA more. Its a ternary encoded program. We have trillions of species. Ffs, lets train a generative model on the distribution of DNAs among all possible life. Then grow it. GANs for generating random organisms anyone? Human 2.0 can probably come about after some of the feature vectors are figured out via PCA on the activations. Just boost feature vector for intelligence. Anyways, yeah! Real matter is already programmable. As programmers its easy to forget that physics says this whole thing is all a monism of information and computation. Code and data. Yin and yang. Even the prime numbers come about as data because of self modifying code. P(0)=2 but all future primes are defined by not being divisible by P(x<n) - think snake eating its own tail and yet growing while doing so. In fact, the most beautiful part about the prime numbers is that they are defined sequentially yet alternative constructions exist which are `atomic`. It is odd that something defined in such a sequential process would form a beautiful structure that can be reduced to direct construction. Relatedly, we see this all the time with recursive functions being turned into procedural ones or functional style data pipleline transformations. The ordering is actually irrelevant to the chaos that the primes display between multiplication and addition. That is, if you defined the first prime as 3 you would yield an entirely different set of primes. For example, 4 would be prime. Beurling figured this out and a lot more through what he called Generalized Primes [1]. [1] https://bookstore.ams.org/surv-213 https://bookstore.ams.org/surv-213
taejo 7y ago
The lamp is not a programmable light-processor that can compute arbitrary computation using light, but Sycamore is (though it's very small). The trouble is we don't know many (any?) interesting algorithms to run on such processors. We can factor prime numbers using Shor's algorithm, but the numbers we can factor with 54 qubits are so small that our best non-quantum algorithms on our best non-quantum computers far outperform them. No supremacy is demonstrated. It's only when one takes problems that are ideally suited to run on this processor that it outperforms classical computers. Even with the deck stacked this way, it's taken until 2019 for it to be done for the first time! It's a very, very early milestone.
- SamBam 7y ago
  Exactly. If we could design some cool lens-refraction based punch card, such that when you shone your desk lamp through it, it solved some very hard problem, then that would also be an incredibly cool solution.
  - samfriedman 7y ago
    Funnily enough, something similar has been done with neural networks "physical-ized" in special glass panes. https://www.osapublishing.org/prj/abstract.cfm?uri=prj-7-8-823 https://www.osapublishing.org/prj/abstract.cfm?uri=prj-7-8-8...
    - lovecg 7y ago
      This is the most amazing thing I’ve seen all day! Has something like this been actually demonstrated beyond the theoretical possibility?
- OskarS 7y ago
  That does make sense, but given that the task is not solving anything "outside" the physical process itself, it still feels unfulfilling. Using my (maybe wrongheaded) analogy: it feels like "we built a lamp to simulate what happens when we turn on a lamp". Quantum "supremacy" only feels like a real thing when a quantum computer can solve a problem that isn't directly tied to the simulation of itself. That's my feeling, anyway. BTW: this is not to disparage the work itself. This seems like great research, and great progress in this field. Good on Google and the researchers!
jhrmnn 7y ago
AFAIK, the main difference between measuring (running) their device and measuring, say, the electron density of a molecule is supposed to be that their chip is easily programmable (in the computer science sense).
deleted 7y ago
[deleted]

by OskarS 7y ago

goldenkey 7y ago

Pretty much. Which is why it is beyond silly we aren't using DNA more. Its a ternary encoded program. We have trillions of species. Ffs, lets train a generative model on the distribution of DNAs among all possible life. Then grow it. GANs for generating random organisms anyone? Human 2.0 can probably come about after some of the feature vectors are figured out via PCA on the activations. Just boost feature vector for intelligence. Anyways, yeah! Real matter is already programmable. As programmers its easy to forget that physics says this whole thing is all a monism of information and computation. Code and data. Yin and yang. Even the prime numbers come about as data because of self modifying code. P(0)=2 but all future primes are defined by not being divisible by P(x<n) - think snake eating its own tail and yet growing while doing so. In fact, the most beautiful part about the prime numbers is that they are defined sequentially yet alternative constructions exist which are `atomic`. It is odd that something defined in such a sequential process would form a beautiful structure that can be reduced to direct construction. Relatedly, we see this all the time with recursive functions being turned into procedural ones or functional style data pipleline transformations. The ordering is actually irrelevant to the chaos that the primes display between multiplication and addition. That is, if you defined the first prime as 3 you would yield an entirely different set of primes. For example, 4 would be prime. Beurling figured this out and a lot more through what he called Generalized Primes [1]. [1] https://bookstore.ams.org/surv-213 https://bookstore.ams.org/surv-213

taejo 7y ago

The lamp is not a programmable light-processor that can compute arbitrary computation using light, but Sycamore is (though it's very small). The trouble is we don't know many (any?) interesting algorithms to run on such processors. We can factor prime numbers using Shor's algorithm, but the numbers we can factor with 54 qubits are so small that our best non-quantum algorithms on our best non-quantum computers far outperform them. No supremacy is demonstrated. It's only when one takes problems that are ideally suited to run on this processor that it outperforms classical computers. Even with the deck stacked this way, it's taken until 2019 for it to be done for the first time! It's a very, very early milestone.

SamBam 7y ago
Exactly. If we could design some cool lens-refraction based punch card, such that when you shone your desk lamp through it, it solved some very hard problem, then that would also be an incredibly cool solution.
- samfriedman 7y ago
  Funnily enough, something similar has been done with neural networks "physical-ized" in special glass panes. https://www.osapublishing.org/prj/abstract.cfm?uri=prj-7-8-823 https://www.osapublishing.org/prj/abstract.cfm?uri=prj-7-8-8...
  - lovecg 7y ago
    This is the most amazing thing I’ve seen all day! Has something like this been actually demonstrated beyond the theoretical possibility?
OskarS 7y ago
That does make sense, but given that the task is not solving anything "outside" the physical process itself, it still feels unfulfilling. Using my (maybe wrongheaded) analogy: it feels like "we built a lamp to simulate what happens when we turn on a lamp". Quantum "supremacy" only feels like a real thing when a quantum computer can solve a problem that isn't directly tied to the simulation of itself. That's my feeling, anyway. BTW: this is not to disparage the work itself. This seems like great research, and great progress in this field. Good on Google and the researchers!

jhrmnn 7y ago

AFAIK, the main difference between measuring (running) their device and measuring, say, the electron density of a molecule is supposed to be that their chip is easily programmable (in the computer science sense).

deleted 7y ago

[deleted]