10 ms·

Quantum Computers. Not like I'm five, but like I'm a software engineer who has a pretty decent understanding of how a classical turing machine works. I can't te

• KhoomeiK 6y ago
  I had an aha moment with quantum computers a few months ago when reading an article that explained it as probability distributions. I don't think I have the complete understanding in my mind anymore and I wish I had saved the article, but looking into how quantum computers essentially serve as probability distribution crunching machines might help with your understanding.
  • arkanciscan 6y ago
    So can they still do traditional deterministic(?) calculations? Or would that be somewhat akin to using machine learning to do your taxes; possible but just overkill? I've often heard it said that Quantum Computers can crack cryptographic keys by trying all the possible inputs for a hashing algorithm or something handwavey like that. Are they just spitting out "probable" solutions then? Do you still have to try a handful of the solutions manually just to see which one works?
    • augustt 6y ago
      Here's what Scott Aaronson says in regard to "trying all the possible inputs": https://news.ycombinator.com/item?id=17425474 https://news.ycombinator.com/item?id=17425474
      • deleted 6y ago
        [deleted]
    • bawolff 6y ago
      "Trying all possible solutions" is generally a bad metaphor for quantum computing and will confuse you. (Its more like you start out with all answers being equal probability, and get the wrong answers to somehow cancel each other out making the "right" answer have a high probability) I am not a quantum person but i once saw a geometric explanation for grover's algorithm which kind of made it all make sense to me. (grover's algorithm is the quantum algo you use for problems where you dont know any approach better than brute force. It can bruteforce stuff in O(sqrt(n)) guesses instead of O(n) like a normal computer). Basically, the geometric version was that you start with all possibilities being of equal probability (i.e. an even superposition of all possible states), negate the amplitude of the correct answer, then reflect the amplitudes around a line that is the mean of the amplitudes (do that sqrt(n)) times. The end result is the correct answer has a higher probability than the other answers. I unfortunately can't find the thing where i originally saw this, but they visualized it basically as a bar graph (of the amplitudes of possible states) and it seemed much clearer to me than other explanations i have come across
    • OkayPhysicist 6y ago
      Yeah, they can do deterministic calculations. You just avoid ever putting the quibits in a state where measurement gives probabilistic results. it would, however, be a ridiculous use of technology, like using a Neural net to simulate an XOR
  • sideshowb 6y ago
    Like probability distributions, but they don't just sum when you combine them, they interfere (probability is the square of amplitude, which can be negative). Quantum computing is all about finding ways to hack the interference process to compute more than you otherwise would have.
• elgfare 6y ago
  I recommend Computerphile's videos https://www.youtube.com/playlist?list=PLzg3FkRs7fcRJLgCmpy3oESvT6_difrq5 https://www.youtube.com/playlist?list=PLzg3FkRs7fcRJLgCmpy3o.... I had the same "problem" as you. What finally made me feel I sort of cracked it was those videos. The way I think of it now is: They let you do matrix multiplication. The internal state of the computer is the matrix, and the input is a vector, where each element is represented by a qubit. The elements can have any value 0 to 1, but in the output vector of the multiplication, they are collapsed into 0 or 1. You then run it many times to get statistical data on the output to be able to pinpoint the output values more closely.
  • ad404b8a372f2b9 6y ago
    I don't know if it's accurate (because I never understand anything I read about it) but this is the most concise and clear explanation I've read on this subject to date. Thank you!
    • dreamcompiler 6y ago
      It's accurate. QC is just linear algebra with complex numbers, plus probability extended to the complex domain. Why that's useful is something I'm still struggling with as well.
      • sodafountan 6y ago
        I'd assume it's the speed advantage, but the only problem I can think of that would require that type of exponential speed is cracking hashing algorithms which just seems destructive and counterproductive, like building a digital nuclear bomb - and from my very limited understanding that's a long ways off from being achieved. I assume there's probably many more complex computational problems outside of my domain that QC can help with. Does anybody know of any?
        • skosch 6y ago
          Many problems require lots of huge matrix multiplications—think simulations of physical systems, i.e. weather systems or molecular interactions, or numerical optimization.
• twomoretime 6y ago
  In short I'd say you need to understand the underlying mathematics to intuitively understand the operations that underpinn the algorithms. And since this is quantum mechanics...there's no real ELI5 version that can give you any useful understanding.
• __sy__ 6y ago
  Since no one has listed it yet, please check out https://quantum.country/ https://quantum.country/ It's by Andy Matuschak and Michael Nielsen, and it is excellent. Have fun!
  • cloogshicer 6y ago
    Yes! How come this isn't higher up in the list? This is one of the best pieces of education I've ever seen. Absolutely wonderful.
  • nagarjun 6y ago
    This deserves to be upvoted all the way to the top!
  • gigama 6y ago
    upvoted
• 7thaccount 6y ago
  There is a comic (maybe SMBC) that covers the whole commonly false belief surrounding qubits.
  • klmadfejno 6y ago
    https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3 The basic gist I get is that quantum computing, for a very specific set of problems, like optimization, let's you search the space more efficiently. With quantum mechanics you can associate computations with positive or negative probability amplitudes. With the right design, you cause multiple paths to incorrect answers to have opposite amplitudes, so that interference causes them to cancel out and not actually happen to begin with. That's just my reading of the comic over and over though.
    • mda 6y ago
      I found the comic not very good either. Kid suddenly blurts "Wait a minute, that means a qubit corresponds to a unit vector in 2 dimensional Hilbert space" Yeah.
      • 7thaccount 6y ago
        I think you have to take that sarcastically like when she mentions that it's not like the classical probability taught in preschool.
      • klmadfejno 6y ago
        Not quite what I meant. I think the comic is excellent. In case its not painfully obvious, the joke is equating lay people's poor understanding of quantum mechanics to a child's misunderstanding of sex. It's not trying to dumb down the concept of quantum computers at all, it's just trying to point out how incorrect how dumb pop science simplifications of it are. The 'qubits are bits with a range of value between 0 and 1 that use quantum magic to test all possibilities at once' is utter fiction.
        • 6y ago
• drocan 6y ago
  not quantum computers per se but I had my aha moment when I saw quantum computing as "linear algebra with probability coefficients". It's mostly working on superpositioned qubits while doing the calculation and then making them (with linear transformations) as likely as possible to collapse on the solution (when "measured").
• McTossOut 6y ago
  Entanglement and interference are computing resources like SPACE, or TIME, with space and time still being represented, because quantum computation is a superset of normal computation (according to the quantum church turing thesis). The substrate of quantum computing enables quantum parallelism (a register equally likely to be all possible integers, for example) and quantum interference (operations that can funnel such values).
• corysama 6y ago
  There’s an O’Reilly book on Programing Quantum Computers that explains it really well. Bonus: it was written by Batman.
• whytai 6y ago
  Here is a video of a researcher at Microsoft Quantum lecturing on this: https://www.youtube.com/watch?v=F_Riqjdh2oM https://www.youtube.com/watch?v=F_Riqjdh2oM "Quantum Computing for Computer Scientists.". However, even with understanding how a Quantum Computer works at its most basic level I still have difficulty understanding the more useful Quantum Algorithms: https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm
• 0xff00ffee 6y ago
  Short answer: there isn't an easy answer. Yet. (Give QC another 50 years). Proof? Just look at all the replies you got: each one is dozens of pages of complex (imaginary) math, control theory, and statistics. The hardest part of QC is exactly what you described: how to extract the answer. There is no algorithm, per se. You build the system to solve the problem. This is why QC is not a general purpose strategy: a quantum computer won't run Ubuntu, but it will be one superfast prime factoring coprocessor, for example (or pathfinder, or root solver). You literally have to build an entire machine to solve just one problem, like factoring. Look at Shor's algorithm: it has a classical algorithm and then a QC "coprocessor" part (think of that like an FPU looking up a transcendental from a ROM: it appears the FPU is computing sin(), but it is not, it is doing a lookup... just an analogy). The entire QC side is custom built just to do this one task: https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm In this example he factors 15 into 5x3, and the QC part requires FFTs and Tensor math. Oy! Like I said, it will take decades for this to become easier to explain. For fun, look at the gates we're dealing with, like "square root of not": https://en.wikipedia.org/wiki/Quantum_logic_gate https://en.wikipedia.org/wiki/Quantum_logic_gate
  • izuchukwu 6y ago
    This feels like the high-level missing piece in my understanding of its use. Do you know any resources that expand on QC’s effective potential more from this point of view?
    • 0xff00ffee 6y ago
      Sorry, I do not.
      • izuchukwu 6y ago
        All good. I appreciate the perspective you’ve given!
    • rootbid 6y ago
      IMO one of the effective potential of a QC is `Secure Encrypted communications`. There is a research project named QUESS (https://en.wikipedia.org/wiki/Quantum_Experiments_at_Space_Scale https://en.wikipedia.org/wiki/Quantum_Experiments_at_Space_S...). This project involves a minisatellite (capable of generating entangled photons in space) to establish a space platform with long-distance satellite and ground quantum channel, and to carry out a series of tests about fundamental quantum principles and protocols in space-based large scale
• bollu 6y ago
  I honestly recommend the following: 1. Pick up the standard textbook by Nielsen and Chuang, Quantum computation and quantum information. read the first two to three chapters. 2. Solve the exercises for the Q# programming language.
• aiisjustanif 6y ago
  I think because it has less applications for traditional "software" and more applications for efficiency of embedded systems. But it could have some bleeding edge new applications from the TCP/IP space for urgent point, new methods for cryptography, or speeding up algorithms for searching. ¯\_(ツ)_/¯
  • bawolff 6y ago
    Im not an expert on quantum computers but I'm not aware of any applications in the embedded space. Generally quantum computers are good for three things * factoring numbers (and other highly related order-finding problems). RIP RSA, but not that applicable outside of crypto. * unstructured search (brute forcing a problem in only O(sqrt(n)) gueses instead of an average of n/2 gueses). Certainly useful...but its not a big enough speedup to be earth shattering. * simulating various quantum systems (so scientists can do experiments easier). Probably by far the most useful/practical application in the near/medium term. There's not a whole lot else they are good for (that we know of, yet)
• dirkt 6y ago
  Very simplified explanation: If you understand Turing Machines, you probably also understand other automata. So you probably understand nondeterministic automata [1]. A quantum computer is like a very restricted nondeterministic automaton, except that the "do several things a once" is implemented in physics. That means just like a NFA can be exponential faster than a DFA, a QC can be exponential faster than a normal computer. But the restriction on QCs makes that a lot harder to do, and so far it only works for some algorithms. As to why quantum physics allows some kind of nondeterminism: If you look at particles as waves, instead of a single location you get a probability function that tells you "where the particle is". So a particule can be "in several places at once". In the same way a qbit can have "several states at once". > What I don't understand is how a programmer is supposed to determine the correct solution when their computer is out in some crazy multiverse. Because one way to explain quantum physics is to say that the waveform can "collapse" [2] and produce a single result, as least as far as the observers are concerned. There are other interpretations of this effect, and this effect is what makes quantum physics counterintuitive and hard to understand. [1] https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.wikipedia.org/wiki/Nondeterministic_finite_automa... [2] https://en.wikipedia.org/wiki/Wave_function_collapse https://en.wikipedia.org/wiki/Wave_function_collapse
  • elorant 6y ago
    The thing I don't understand about qc is how on earth can you read values from qbits without breaking superposition.
    • cyphar 6y ago
      You can't, it's a fundamental aspect of quantum mechanics (measuring any entangled system collapses it because you've forced the system into a state by measuring it). The idea is that you structure the QC system such that the computation is done using entangled states, but when it comes to measuring the qubits (to get the result of the computation) the state is such that you'll get meaningful results. This means the quantum state at the end of the calculation would ideally be along whatever axes you're measuring, so you get the same answer 100% of the time.
• ruggeri 6y ago
  I found Quantum Computing Without The Physics epicly helpful. https://arxiv.org/abs/1708.03684 https://arxiv.org/abs/1708.03684 It explains in terms a computer scientist can understand. As in: it sets out a computational model and explores it, regardless whether we can physically realize that machine. Hope this helps!
  • ksnape 6y ago
    Not sure if it has helped anyone else, but it did me!
• deleted 6y ago
  [deleted]
  • deleted 6y ago
    [deleted]
• drran 6y ago
  Qubit is physical random generator, which quickly oscillates between 0 and 1. It does that so quickly, so scientists must operate with probabilities to perform calculations. They create analog quantum computers, where right solutions are much more probable than wrong ones, then let system to figure them out, then sample solutions periodically.
• maest 6y ago
  IBM's Quantum Experience is great for this. It walks you through the quantum gates you can use and lets you write small programs for quantum processors. I've found that to be the clearest way of understanding what qcs do.
• aliceryhl 6y ago
  This podcast episode has an amazing explanation by one of the top researchers in the field: https://www.youtube.com/watch?v=uX5t8EivCaM https://www.youtube.com/watch?v=uX5t8EivCaM The basic idea is that by making the amplitudes of the qubits destructively interfere with each other in certain ways, you can eliminate all of the wrong answers to the question you're trying to answer.
• skocznymroczny 6y ago
  I looked briefly at QCs and I understood them as kind of a machine that doesn't try every possible solution. It is in every possible solution, and then you can somehow "lock it" in the state that is the solution to your problem. Kind of like NP problems are hard to find a solution but easy to verify a solution.
• cousin_it 6y ago
  I think there's no way to understand quantum computing without first understanding some linear algebra, specifically tensor products. How ten 2-dimensional spaces give rise to a 1024-dimensional space, how the Kronecker product of three 2x2 matrices is an 8x8 matrix, and so on. If you're comfortable with that, here's a simple and precise explanation of quantum computing: 1) The state of an n-qubit system is a 2^n dimensional vector of length 1. You can assume that all coordinates are real numbers, because going to complex numbers doesn't give more computational power. 2) You can initialize the vector by taking an n-bit string, interpreting it as a number k, and setting the k'th coordinate of the vector to 1 and the rest to 0. 3) You cannot read from the vector, but exactly once (destroying the vector in the process) you can use it to obtain an n-bit string. For all k, the probability of getting a string that encodes k is the square of the k'th coordinate of the vector. Since the vector has length 1, all probabilities sum to 1. 4) Between the write and the read, you can apply certain orthogonal matrices to the vector. Namely, if we interpret the 2^n dimensional space as a tensor product of n 2-dimensional spaces, then we'll count as an O(1) operation any orthogonal matrix that acts nontrivially on only O(1) of those spaces, and identity on the rest. (This is analogous to classical operations that act nontrivially on only a few bits, and identity on the rest.) The computational power comes from the huge size of matrices described in (4). For example, if a matrix acts nontrivially on one space in the tensor product and as identity on nine others, then mathematically it's a 1024x1024 matrix consisting of 512 identical 2x2 blocks - but physically it's a simple device acting on one qubit in constant time and not even touching the other nine.
  • andyjohnson0 6y ago
    Thank you for posting such a concise description.
  • tabtab 6y ago
    What about some kind of interactive simulation, kind of like playing with a graphing calculator? People tend to relate to things better by tinkering and playing with parameters to observe the impact on results. Analog experimentation is how we learned most Newtonian physics.
    • 6y ago
• fnrslvr 6y ago
  I wrote a basic response, but it got longer than I thought it would and HN complained about it being too long, so here's a pastebin: https://pastebin.com/zTJA4bJh https://pastebin.com/zTJA4bJh
• hyperbovine 6y ago
  you're in luck my friend. Perl has had a quantum computing module since the late 90s: https://metacpan.org/pod/Quantum::Superpositions https://metacpan.org/pod/Quantum::Superpositions As far as I can tell this one still outperforms all existing "hardware implementations".
  • qorrect 6y ago
    The first 'meetup' I went to some 20 years ago was on this module!
• locuscoeruleus 6y ago
  Pseudo-code for quantum computers is currently linear algebra. Fortunately, most programmers have the required linear algebra to get a thorough understanding of the basics! Check this out https://quantum.country/qcvc https://quantum.country/qcvc. Fair warning, I did have to brush up on my linear algebra a bit, but it's worth it imo. Friends in the know say that when you understand this article, you understand quantum computers.
• lambdatronics 6y ago
  Nobody understands quantum mechanics. Lots of people know how to apply it. I don't think quantum technology is going to go anywhere until physicists revamp the theory & the pedagogy in a way that makes it comprehensible. I say this as someone who passed 2 semesters of graduate QM.
  • 0xff00ffee 6y ago
    > I say this as someone who passed 2 semesters of graduate QM. THat's funny because my EE math concentration was on advanced calculus. I took two semesters of a-calc and got A's, but I only know how to compute a Jacobian and apply it, not its origin story. It's a very weird feeling to understand the motions but not the ... depth?