Write Your First Quantum Program (Common Lisp) | Hacker News Reader

Write Your First Quantum Program (Common Lisp)

lambdafaktorie.com

107 pointsmedo-bear25 comments

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=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

[4] https://www.cambridge.org/pt/academic/subjects/physics/quant...

What boom would you suggest for a physics based approach to QC? Other than a solid understanding of quantum theory of course

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

[2] https://iopscience.iop.org/article/10.1088/1367-2630/18/2/02...

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.

> 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

[2] https://gilkalai.wordpress.com/

> 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.

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/en...

> 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).

My understanding was that quantum supremacy occurs when a quantum computer performs a computation that cannot be performed with comparable speed on a classical computer given the best available classical hardware and the best available classical algorithms of the time. In particular, it does not require a proof that no efficient classical algorithm exists. Instead, it is sufficient that nobody knows such a classical algorithm at the time of demonstration.

Otherwise even factoring a large number by running Shor's algorithm on an error corrected quantum computer would still not constitute quantum supremacy demonstration because there is no proof that factoring cannot be done efficiently on a classical computer. After all, it is not inconceivable that people just don't know how to factor integers fast on a classical computer.

I agree, but the argument holds --- in particular I'm thinking of Google's supremacy experiment, where they did do something that, taken as a generic process, would require resources beyond "the best available classical hardware and the best available classical algorithms of the time". However, people play catch-up, and end up coming up with classical approaches for that particular experiment. Of course, factoring is a special and very strong case that is less susceptible to this.

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.

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.

What topology do you have in mind when referring to "the topology"?

I was thinking of which physical qubits are connected to each other.

> 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 :)

>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.

The physical properties of 'non-quantum' computing are so baked in, in-grained, and abstracted in standard ways that we don't have to think about them very much -- and I think that abstractionism is the essence of the magic power of programming. But when I learned C it really helped me to know what was going on 'behind' the compiler, on the hardware.

As a programmer of apps and widgets I only need to know the rules of the game that my framework and language exposes, and I think it probably always helps to have a bigger context, but I think it is increasingly less necessary for getting stuff done.

With quantum, the entire stack is different. Like a computer from an alternate universe ;) So that whole stack has to be built up again.

But I think abstraction and encapsulation is going to allow many (most?) programmers to use the quantum computer without ever having to know what's going on behind the keyboard and the screen, just like our normal computers now.

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.

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.

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!

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.

Thanks for the correction - there seems to be no date on the article, and the HN title needs a [2004] in that case.

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?

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

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

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

I did not notice that feature when browsing on my ipad

Reply on news.ycombinator.com