One key aspect of that is that all of the qubits are entangled. The qubit isn't in more than two states, but in 2 states at once, and N qubits are in 2^N states at once. It's not quite as simple as that: you can't really just set up any algorithm in a quantum computer the way you would with a classical one. But for those problems amenable to quantum computation (including, notably, prime factoring), they can be solved very fast.
With 2^53 qubits we should be able to factor some very, very large prime numbers.
https://www.schneier.com/blog/archives/2009/09/quantum_compu...
>Instead, it came up with an answer to the "order-finding routine," the "computationally hard" part of Shor's algorithm that requires a quantum calculation to solve the problem in a reasonable amount of time.
They weren't the first team to do this, either, they just miniaturized parts of the hardware.
If I'm wrong and IBM's latest "quantum computer" can actually do the Shor algorithm on the number 15 using 4608 gate operations, I will publically eat one of my shoes like Werner Herzog. Assuming I can get someone else to take the other side of the bet, of course.
> the chip itself didn't just spit out 5 and 3. Instead, it came up with an answer to the "order-finding routine"
O noes! The quantum computer only did the "order-finding" part of Shor's algorithm! ... But wait. Here's the Wikipedia page for Shor's algorithm:
> Shor's algorithm consists of two parts: 1. A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding. 2. A quantum algorithm to solve the order-finding problem.
So, the article GP cited says that a quantum computer did the part of factoring the number 15 that actually uses a quantum computer. Nothing wrong with that.
The article's link to the actual paper is broken, which makes it harder to tell whether as you say they cheated somehow, but here's another article about factoring 15 with a quantum computer https://science.sciencemag.org/content/351/6277/1068 which so far as I can see claims to have actually done the whole of (the relevant part of) Shor's algorithm on actual QC hardware.
Can you explain this a little more? I've seen similar references to this elsewhere. If it means what I think it means, it's kind of a really big deal. But it may mean something else.
The paper I linked to says, e.g., the following:
> Subsequent multipliers can similarly be replaced with maps by considering only possible outputs of the previous multiplications. However, using such maps will become intractable, [...] Thus, controlled full modular multipliers should be implemented.
So in at least one case they are explicitly not taking a particular shortcut because it doesn't scale to factorizing larger numbers. If you say they are taking other shortcuts that don't scale by "leaving out the gates to the wrong answer", then I think you owe us an actual explanation of what shortcuts they are taking and how you know you're taking them, rather than just a link to a paper from 1996 that says how to take some shortcuts.
It's not my fault you believe in press releases without understanding what they mean.
The paper I linked to (1) doesn't cite Preskill et al and (2) explicitly claims not to be taking shortcuts that don't generalize to numbers other than 15; as well as the bit I quoted earlier, they say "for a demonstration of Shor’s algorithm in a scalable manner, special care must be taken to not oversimplify the implementation—for instance, by employing knowledge about the solution before the actual experimental application" and cite an article in Nature decrying cheaty oversimplifications of Shor's algorithm.
I don't see anything in their description of what they do that seems to me to match your talk of "deleting the gates that lead to the wrong answer".
(The Kitaev paper they cite also doesn't cite Preskill et al, unsurprisingly since it predates that, and also doesn't contain anything that looks to me like cheaty shortcut-taking.)
It is, of course, possible that that paper does take cheaty shortcuts and I've missed them. It is, of course, possible that its authors are flatly lying about what they're doing, and trying to hide the evidence by not citing important prior papers that told them how to do it. If so, perhaps you could show us where.
Otherwise, I for one will be concluding from the surfeit of bluster and absence of actual information in your comments so far that you're just assuming that every alleged "factoring of 15" is indulging in the dishonesty you think they are, and that you aren't interested in actually checking.
(You don't, indeed, owe anyone anything. It's just that if you want to be taken seriously, that's more likely if you offer something other than sneering and bluster.)
Pointing this out is apparently necessary; I don't know why it triggers people so to point out that virtually the entire field up to the present day has consisted of grandstanding quasi-frauds. And that you apparently have to understand things and read extremely carefully to notice, because whatever honest workers there may be don't see it as in their interest to point such things out as it may upset their rice bowls.
You have someone else in another thread insisting that annealing can factor giant prime numbers which is equally bullshit. Do you expect me to patiently, precisely and (somehow) dispassionately point out every line of bullshit in every quantum computing paper published? The mere fact that the field is pervasive with bullshit, publishes papers and announcements that are known to be bullshit, and promises all kinds of pixie dust bullshit on a regular basis ought to give you some slight skepticism, some Bayesian prior that the grand pronunciamentos of this clown car should be treated with a bit of skepticism.
I'm all in favour of pointing out bullshit. But there's a boy-who-cried-wolf problem if you just indiscriminately claim that everything is the same kind of bullshit without checking it.
Of course that doesn't mean that you're obliged to check everything. You can say "I expect this is bullshit of the usual sort but haven't checked". But if you say "this is bullshit of the usual sort" without checking and it turns out that that isn't the case (it looks to me as if the paper I linked to isn't the kind of bullshit you describe) then you take a credibility hit that makes all your bullshit-spotting much less useful than if you were more careful.
Some people laugh at the chicanery of scumbags who claim fully autonomous vehicles are right around the corner. I laugh at the frauds and mountebanks of "quantum information theory" and the muppets who believe everything they say. De Gustibus.
https://arxiv.org/abs/1301.7007
"Pretending to factor large numbers on a quantum computer (2013)"
"Of course this should not be considered a serious demonstration of Shor’s algorithm. It does, however, illustrate the danger in “compiled” demonstrations of Shor’s algorithm. To varying degrees, all previous factorization experiments have benefited from this artifice. While there is no objection to having a classical compiler help design a quantum circuit (indeed, probably all quantum computers will function in this way), it is not legitimate for a compiler to know the answer to the problem being solved. To even call such a procedure compilation is an abuse of language."
More references:
https://crypto.stackexchange.com/questions/59795/largest-int...
QC is about setting up interference patterns between the qbits, it is fundamentally unlike classical computing. For some problems algorithms can be designed that use those interferences to compute things, like the famous Shor's algorithm for polynomial time prime factoring.
QC speeds things up only in the cases where an asymptotically faster algorithm can be designed this way, it is not a general purpose parallelization mechanism.
And we don't know many things it speeds up for sure! For example: we don't actually know that there isn't a classical polynomial time prime factors algorithm we haven't found. Here is a recent example of a quantum algorithm leading to the discovery of a classical algorithm that is equivalent to the quantum: https://www.quantamagazine.org/teenager-finds-classical-alte...
Not really. From an information theory perspective, holding two states is the most efficient way of computing. Or at least, there is no speed-up gained from doing computations in any other base than 2.
Quantum computers can be in both states at the same time (as far as that interpretation of quantum mechanics goes). So, if you keep the qubits all in this superposition state, you can calculate multiple things at the same time.
Assuming the cost of operations on each digit is a multiple of its number of states, the most efficient base for computing with arbitrary numbers is 3, which is the closest integer to the optimal base e:
From a physical perspective, holding two states is the most efficient way of computing. I.e. the electronics required to compute in bases other than 2 involve higher power and present difficult challenges.
Explains to 5 different levels of CS knowledge.
>> that can hold more than 2 states
--> that can hold more than 2 states AT THE SAME TIME (in weird quantum conditions)
So you're not trying 00, 01, 10, 11; you're trying [00|01|10 |11] at the same time, as well as other state in between 0 and 1.