5 ms·

Write Your First Quantum Program (Common Lisp)

107 points by medo-bear 6y ago

miguelmurca 6y ago
Hello! PhD student on quantum computing here. While it's cool that the field of QC raises excitement and there are efforts to promote QC to a more general public, it's always a little frustrating to see these approaches that, in a sense (and in my opinion), seriously underplay the difficulty and distance of the field from computer engineering. While it's true that it's an incredibly interdisciplinary field, which can be studied from a Physics, CompSci, EE, etc., perspective, it's definitely its own field, and not a new framework or programming language. I think this reflects heavily on the fact that a lot of QC programming languages peddled by the main industry players hide a lot of stuff behind opaque API calls. The thing is (again, imho!) it wouldn't have made sense to talk about frameworks when the first classical computers appeared --- and you'd better have knowledge about the hardware and theory. (These are still a good idea to know but not really a requirement anymore.) Likewise, I think that for the next decades, anyone who wants to meaningfully contribute to QC (rather than call a few API functions) will have to read some technical stuff (my recommendations are [1] as a semi-informal approach, [2] for a CS approach, [3] for an algorithm overview, and [4] as the reference book). Sorry for the minor rant :) [1] https://www.cambridge.org/catalogue/catalogue.asp?isbn=9781107302105 https://www.cambridge.org/catalogue/catalogue.asp?isbn=97811... [2] Ethan Bernstein, & Umesh Vazirani (1997). Quantum Complexity TheorySIAM Journal on Computing, 26(5), 1411–1473. [3] https://www.springer.com/gp/book/9783030190651 https://www.springer.com/gp/book/9783030190651 [4] https://www.cambridge.org/pt/academic/subjects/physics/quantum-physics-quantum-information-and-quantum-computation/quantum-computation-and-quantum-information-10th-anniversary-edition?format=HB&isbn=9781107002173 https://www.cambridge.org/pt/academic/subjects/physics/quant...
- hvna 6y ago
  What boom would you suggest for a physics based approach to QC? Other than a solid understanding of quantum theory of course
  - miguelmurca 6y ago
    I guess "physics based approach" could mean a few things (for context, my background is physics, not CS), but quantum chemistry [1,2] definitely stands in a very physics-y area while involving QC very directly. There is also QC for solid state physics, for more or less the same reasons you'd use QC for chemistry (scaling problems with the classical solutions). On the other hand, quantum control (physically manipulating your quantum computer) has a lot of physics in it, but also crosses into EE. Likewise, looking into physical systems that can behave as a quantum computer is physics and EE. However I'm very much unfamiliar with that part, so I can't say anything there. [1] https://www.nature.com/articles/ncomms5213 https://www.nature.com/articles/ncomms5213 [2] https://iopscience.iop.org/article/10.1088/1367-2630/18/2/023023/pdf https://iopscience.iop.org/article/10.1088/1367-2630/18/2/02...
- thoweruo34 6y ago
  +1 Thanks for this perspective. I've always thought the whole "yay! let's do quantum programming!" was a bit strange. IIRC we can't really do "real" quantum computation with anything more than a few bits because people can't do QEC to correct for the noise. D-Wave's systems aren't even "real" QCs AFAIK. From a very amateur perspective, it looked like Gil Kalai was arguing that physical realizations would not be impossible, but work at UIST and Google's "quantum supremacy" result, somehow have proved him wrong ? Can you say a bit more on the state of QEC ? Thanks. P.S: The hype of CS these days is really getting tiring; the ridiculuous expectations around "quantum-deeplearning-crypto-neuron-RL" will hopefully not cause another AI winter.
  - C-x_C-f 6y ago
    > From a very amateur perspective, it looked like Gil Kalai was arguing that physical realizations would not be impossible, but work at UIST and Google's "quantum supremacy" result, somehow have proved him wrong ? I assume you meant "would be impossible"? At any rate, from my slightly less amateurish understanding of the subject, I think that the main contrast between Kalai's claims and Google's results boils down to the following: - broadly speaking, Kalai is referring to pure quantum computation, more specifically he is computing limits about the efficiency and energy requirements of computers that work exclusively using quantum/linear logic; - Google's experiment made extensive use of classical computation, and it's unclear to what extent quantum computation actually impacted the result (to the point that some people claim that the entire experiment could be performed classically, see e.g. [1]) Unfortunately, many of the nuances in the debate are lost on me--in the past, I had some forays into the physics and mathematics of QC but was ultimately driven away from the dumb money flowing around--but I would recommend Gil Kalai's blog [2] as it is both accessible and rigorous (albeit being obviously biased toward one side of the argument). [1] https://arxiv.org/abs/2103.03074 https://arxiv.org/abs/2103.03074 [2] https://gilkalai.wordpress.com/ https://gilkalai.wordpress.com/
  - miguelmurca 6y ago
    > Can you say a bit more on the state of QEC ? Thanks. There's not a lot I can say other than what's (I think) more or less common knowledge in the field: QEC is a practical issue, and so is deeply tied to physical implementation, etc. QC however, as an idea, has power in itself; you can define a Turing-like machine that incorporates notions of quantum mechanics, forming complexity classes that are thought to be disjoint from the classical ones (including probabilistic classical machines) (see ref. [2] in the OP). QEC is, then, any strategy that allows you to implement reliable (QC) resources in practice (think classical redundancy). The fact that you are dealing with quantum resources rather than classical makes it harder than CEC. The problem with current technology is that if you don't have QEC you can't really get to a point (resource-wise) where the classical/quantum class separation is relevant. Achieving this separation is what's called "supremacy" (or "advantage"). You can try to sidestep QEC by building quality (as noiseless as possible) quantum computers. > From a very amateur perspective, it looked like Gil Kalai was arguing that physical realizations would not be impossible, but work at UIST and Google's "quantum supremacy" result, somehow have proved him wrong ? Quantum supremacy is debated, and so not something I can reasonably comment on. From the explanation above however, you can see that supremacy is achieved whenever you do something with a QC that cannot be done with a classical computer. The problem is proving that something is 100% provably beyond the scope of a classical computer (people are clever, and so it's often not). However, one thing is to say whether people are achieving quantum supremacy, another is to say whether people are doing quantum computing. For the latter, I would say we definitely are. You can definitely access a quantum computer in the cloud and run routines that can only produce the given outcome if there are quantum effects in play. [1] (Whether or not you could simulate these results classically relates to supremacy, not whether QC is real.) [1] https://quantum-computing.ibm.com/composer/docs/iqx/guide/entanglement https://quantum-computing.ibm.com/composer/docs/iqx/guide/en...
- jcadam 6y ago
  I think part of your issue is there's a lot of interest in QC (given the hype) on the part of "ordinary" computer scientists (I include myself here) who don't have the background in physics to really understand how it works. A lot of people believe this may be the next "big thing." And we're always afraid of being left behind.
- nemoniac 6y ago
  While I understand the source of your frustration, I still think there is plenty to be gained by viewing quantum computing as "a new framework". Just as you might know plenty about programming but little or nothing about electronics or chip fabrication, so too can you learn about the wonders of quantum programming without knowing anything about the physics of the D-Wave Vesuvius processor or whatever. You do need to know enough about the topology, gates, decoherence times, etc. to know how to program the actual platform effectively but you can leave the lower level questions to the experts at that level.
  - C-x_C-f 6y ago
    What topology do you have in mind when referring to "the topology"?
    - nemoniac 6y ago
      I was thinking of which physical qubits are connected to each other.
  - miguelmurca 6y ago
    > Just as you might know plenty about programming but little or nothing about electronics or chip fabrication, so too can you learn about the wonders of quantum programming without knowing anything about the physics of the D-Wave Vesuvius processor or whatever. I think you misunderstand me; I think it's great that people get into QC, and indeed they don't have to know everything from top to bottom (like I don't). I just think that it should be regarded as getting into a specific area of biology, physics, or any other area of science, instead of being equated to learning C when you know Java, or something :)
    - grawprog 6y ago
      >instead of being equated to learning C when you know Java, or something :) I agree, I tried looking into some QC stuff that was presented that way, my impression after was that it's more akin to learning to solder together PCB boards to make a computer from scratch when all you know is basic HTML.
- kvathupo 6y ago
  I wouldn't totally discount the post; the program itself seems to be on the level of FPGAs by specifying individual gates. I agree that it hides a lot of nitty-gritty like error correction and QRAM, but in an ideal world, this is what "quantum programmers" should do, just as modern day programmers don't worry about error correction and capacitors losing charge.
- randomsearch 6y ago
  Have worked in QC. You make a good point. There’s a lot of bandwagoning via producing fairly trivial libraries. To get into QC, to understand what’s going on, you’re better to learn a bit of linear algebra and follow some introductory lecture. IMO this effort is worth it to discover how quantum error correction works, because it really is quite mind blowing when the penny first drops... perhaps only recursion also had that effect on me.
yellowyacht 6y ago
OT: When I select text on this page, it drags like it is an image. It is both weird and not user friendly. I select text to help read and follow long sentences. Is this some sort of anti-copy-paste mechanism? If so, the text is in the source so it's not useful
- kdmdmdmmdmd 6y ago
  I did not notice that feature when browsing on my ipad
phoe-krk 6y ago
Nitpick: as a CL programmer, I shuddered when I noticed that they use SLIME from 2014. It can work, sure, but it's ancient by now!
- lispm 6y ago
  Sure, but the article wasn't written now. It's an old article. The SLIME version gives you an indication when the article was published: somewhen not too long after 2014. The original QGAME code is from 1999-2004.
  - phoe-krk 6y ago
    Thanks for the correction - there seems to be no date on the article, and the HN title needs a [2004] in that case.
nahuel0x 6y ago
Not to be picky, but what are the advantages of using CL for this kind of software instead of Julia?
- lispm 6y ago
  I guess one of the advantages here is that the original author, who wrote it 1999 onwards, did not have to wait 10+ years for Julia to be released in 2012. ;-) He just used a language, which was available then. http://faculty.hampshire.edu/lspector/qgame.html http://faculty.hampshire.edu/lspector/qgame.html
uhhhhhhhhhhhhhh 6y ago
grep --use-quantum-nfa
throwaway8581 6y ago
Are quantum computers compatible with all not-disproven interpretations of quantum mechanics? Including unpopular ones like, e.g., local/global hidden variable theories. What I mean is, do we actually know for sure that quantum computers do what we want them to do?

107 points by medo-bear 6y ago

Hello! PhD student on quantum computing here. While it's cool that the field of QC raises excitement and there are efforts to promote QC to a more general public, it's always a little frustrating to see these approaches that, in a sense (and in my opinion), seriously underplay the difficulty and distance of the field from computer engineering. While it's true that it's an incredibly interdisciplinary field, which can be studied from a Physics, CompSci, EE, etc., perspective, it's definitely its own field, and not a new framework or programming language. I think this reflects heavily on the fact that a lot of QC programming languages peddled by the main industry players hide a lot of stuff behind opaque API calls. The thing is (again, imho!) it wouldn't have made sense to talk about frameworks when the first classical computers appeared --- and you'd better have knowledge about the hardware and theory. (These are still a good idea to know but not really a requirement anymore.) Likewise, I think that for the next decades, anyone who wants to meaningfully contribute to QC (rather than call a few API functions) will have to read some technical stuff (my recommendations are [1] as a semi-informal approach, [2] for a CS approach, [3] for an algorithm overview, and [4] as the reference book). Sorry for the minor rant :) [1] https://www.cambridge.org/catalogue/catalogue.asp?isbn=9781107302105 https://www.cambridge.org/catalogue/catalogue.asp?isbn=97811... [2] Ethan Bernstein, & Umesh Vazirani (1997). Quantum Complexity TheorySIAM Journal on Computing, 26(5), 1411–1473. [3] https://www.springer.com/gp/book/9783030190651 https://www.springer.com/gp/book/9783030190651 [4] https://www.cambridge.org/pt/academic/subjects/physics/quantum-physics-quantum-information-and-quantum-computation/quantum-computation-and-quantum-information-10th-anniversary-edition?format=HB&isbn=9781107002173 https://www.cambridge.org/pt/academic/subjects/physics/quant...

hvna 6y ago
What boom would you suggest for a physics based approach to QC? Other than a solid understanding of quantum theory of course
- miguelmurca 6y ago
  I guess "physics based approach" could mean a few things (for context, my background is physics, not CS), but quantum chemistry [1,2] definitely stands in a very physics-y area while involving QC very directly. There is also QC for solid state physics, for more or less the same reasons you'd use QC for chemistry (scaling problems with the classical solutions). On the other hand, quantum control (physically manipulating your quantum computer) has a lot of physics in it, but also crosses into EE. Likewise, looking into physical systems that can behave as a quantum computer is physics and EE. However I'm very much unfamiliar with that part, so I can't say anything there. [1] https://www.nature.com/articles/ncomms5213 https://www.nature.com/articles/ncomms5213 [2] https://iopscience.iop.org/article/10.1088/1367-2630/18/2/023023/pdf https://iopscience.iop.org/article/10.1088/1367-2630/18/2/02...
thoweruo34 6y ago
+1 Thanks for this perspective. I've always thought the whole "yay! let's do quantum programming!" was a bit strange. IIRC we can't really do "real" quantum computation with anything more than a few bits because people can't do QEC to correct for the noise. D-Wave's systems aren't even "real" QCs AFAIK. From a very amateur perspective, it looked like Gil Kalai was arguing that physical realizations would not be impossible, but work at UIST and Google's "quantum supremacy" result, somehow have proved him wrong ? Can you say a bit more on the state of QEC ? Thanks. P.S: The hype of CS these days is really getting tiring; the ridiculuous expectations around "quantum-deeplearning-crypto-neuron-RL" will hopefully not cause another AI winter.
- C-x_C-f 6y ago
  > From a very amateur perspective, it looked like Gil Kalai was arguing that physical realizations would not be impossible, but work at UIST and Google's "quantum supremacy" result, somehow have proved him wrong ? I assume you meant "would be impossible"? At any rate, from my slightly less amateurish understanding of the subject, I think that the main contrast between Kalai's claims and Google's results boils down to the following: - broadly speaking, Kalai is referring to pure quantum computation, more specifically he is computing limits about the efficiency and energy requirements of computers that work exclusively using quantum/linear logic; - Google's experiment made extensive use of classical computation, and it's unclear to what extent quantum computation actually impacted the result (to the point that some people claim that the entire experiment could be performed classically, see e.g. [1]) Unfortunately, many of the nuances in the debate are lost on me--in the past, I had some forays into the physics and mathematics of QC but was ultimately driven away from the dumb money flowing around--but I would recommend Gil Kalai's blog [2] as it is both accessible and rigorous (albeit being obviously biased toward one side of the argument). [1] https://arxiv.org/abs/2103.03074 https://arxiv.org/abs/2103.03074 [2] https://gilkalai.wordpress.com/ https://gilkalai.wordpress.com/
- miguelmurca 6y ago
  > Can you say a bit more on the state of QEC ? Thanks. There's not a lot I can say other than what's (I think) more or less common knowledge in the field: QEC is a practical issue, and so is deeply tied to physical implementation, etc. QC however, as an idea, has power in itself; you can define a Turing-like machine that incorporates notions of quantum mechanics, forming complexity classes that are thought to be disjoint from the classical ones (including probabilistic classical machines) (see ref. [2] in the OP). QEC is, then, any strategy that allows you to implement reliable (QC) resources in practice (think classical redundancy). The fact that you are dealing with quantum resources rather than classical makes it harder than CEC. The problem with current technology is that if you don't have QEC you can't really get to a point (resource-wise) where the classical/quantum class separation is relevant. Achieving this separation is what's called "supremacy" (or "advantage"). You can try to sidestep QEC by building quality (as noiseless as possible) quantum computers. > From a very amateur perspective, it looked like Gil Kalai was arguing that physical realizations would not be impossible, but work at UIST and Google's "quantum supremacy" result, somehow have proved him wrong ? Quantum supremacy is debated, and so not something I can reasonably comment on. From the explanation above however, you can see that supremacy is achieved whenever you do something with a QC that cannot be done with a classical computer. The problem is proving that something is 100% provably beyond the scope of a classical computer (people are clever, and so it's often not). However, one thing is to say whether people are achieving quantum supremacy, another is to say whether people are doing quantum computing. For the latter, I would say we definitely are. You can definitely access a quantum computer in the cloud and run routines that can only produce the given outcome if there are quantum effects in play. [1] (Whether or not you could simulate these results classically relates to supremacy, not whether QC is real.) [1] https://quantum-computing.ibm.com/composer/docs/iqx/guide/entanglement https://quantum-computing.ibm.com/composer/docs/iqx/guide/en...
jcadam 6y ago
I think part of your issue is there's a lot of interest in QC (given the hype) on the part of "ordinary" computer scientists (I include myself here) who don't have the background in physics to really understand how it works. A lot of people believe this may be the next "big thing." And we're always afraid of being left behind.
nemoniac 6y ago
While I understand the source of your frustration, I still think there is plenty to be gained by viewing quantum computing as "a new framework". Just as you might know plenty about programming but little or nothing about electronics or chip fabrication, so too can you learn about the wonders of quantum programming without knowing anything about the physics of the D-Wave Vesuvius processor or whatever. You do need to know enough about the topology, gates, decoherence times, etc. to know how to program the actual platform effectively but you can leave the lower level questions to the experts at that level.
- C-x_C-f 6y ago
  What topology do you have in mind when referring to "the topology"?
  - nemoniac 6y ago
    I was thinking of which physical qubits are connected to each other.
- miguelmurca 6y ago
  > Just as you might know plenty about programming but little or nothing about electronics or chip fabrication, so too can you learn about the wonders of quantum programming without knowing anything about the physics of the D-Wave Vesuvius processor or whatever. I think you misunderstand me; I think it's great that people get into QC, and indeed they don't have to know everything from top to bottom (like I don't). I just think that it should be regarded as getting into a specific area of biology, physics, or any other area of science, instead of being equated to learning C when you know Java, or something :)
  - grawprog 6y ago
    >instead of being equated to learning C when you know Java, or something :) I agree, I tried looking into some QC stuff that was presented that way, my impression after was that it's more akin to learning to solder together PCB boards to make a computer from scratch when all you know is basic HTML.
kvathupo 6y ago
I wouldn't totally discount the post; the program itself seems to be on the level of FPGAs by specifying individual gates. I agree that it hides a lot of nitty-gritty like error correction and QRAM, but in an ideal world, this is what "quantum programmers" should do, just as modern day programmers don't worry about error correction and capacitors losing charge.
randomsearch 6y ago
Have worked in QC. You make a good point. There’s a lot of bandwagoning via producing fairly trivial libraries. To get into QC, to understand what’s going on, you’re better to learn a bit of linear algebra and follow some introductory lecture. IMO this effort is worth it to discover how quantum error correction works, because it really is quite mind blowing when the penny first drops... perhaps only recursion also had that effect on me.

yellowyacht 6y ago

OT: When I select text on this page, it drags like it is an image. It is both weird and not user friendly. I select text to help read and follow long sentences. Is this some sort of anti-copy-paste mechanism? If so, the text is in the source so it's not useful

kdmdmdmmdmd 6y ago
I did not notice that feature when browsing on my ipad

phoe-krk 6y ago

Nitpick: as a CL programmer, I shuddered when I noticed that they use SLIME from 2014. It can work, sure, but it's ancient by now!

lispm 6y ago
Sure, but the article wasn't written now. It's an old article. The SLIME version gives you an indication when the article was published: somewhen not too long after 2014. The original QGAME code is from 1999-2004.
- phoe-krk 6y ago
  Thanks for the correction - there seems to be no date on the article, and the HN title needs a [2004] in that case.

nahuel0x 6y ago

Not to be picky, but what are the advantages of using CL for this kind of software instead of Julia?

lispm 6y ago
I guess one of the advantages here is that the original author, who wrote it 1999 onwards, did not have to wait 10+ years for Julia to be released in 2012. ;-) He just used a language, which was available then. http://faculty.hampshire.edu/lspector/qgame.html http://faculty.hampshire.edu/lspector/qgame.html

uhhhhhhhhhhhhhh 6y ago

grep --use-quantum-nfa

throwaway8581 6y ago

Are quantum computers compatible with all not-disproven interpretations of quantum mechanics? Including unpopular ones like, e.g., local/global hidden variable theories. What I mean is, do we actually know for sure that quantum computers do what we want them to do?