7 ms·

Quantum Algorithm Implementations for Beginners

110 points by rg111 4y ago

elondaits 4y ago
Unfortunately every page of the document has the words "Just accepted" across the whole page making it almost unreadable (as in: can be read, but it's painful)
- ketanmaheshwari 4y ago
  I have a copy without any watermarks. How should I share it here or share with you?
  - __rito__ 4y ago
    Not GP, but, can you send me via email? Email on bio.
- jcarreiro 4y ago
  You can download a version without the watermarks from arXiv: https://arxiv.org/abs/1804.03719 https://arxiv.org/abs/1804.03719.
deleted 4y ago
[deleted]
isoprophlex 4y ago
Not trolling: is there really a need to train a cohort of quantum programmers? Can these computers actually do something better than their classical counterparts, right now?
- samstave 4y ago
  I, for one, welcome any learning. So even if I am never actually to program a quantum computer, Why would I not like to know how to do such? Why should the ability/knowledge be hidden from any body. But you'll never know, until you look at me.
  - rusticpenn 4y ago
    You can program a quantum computer today, ibm quantum computing cloud provides all 5qubit computing for free.
    - dr_dshiv 4y ago
      Also see Quantum Inspire for free, accessible quantum computing on the cloud: https://www.quantum-inspire.com/ https://www.quantum-inspire.com/
- dr_dshiv 4y ago
  > Can these computers actually do something better than their classical counterparts, right now? You could say quantum computers do something better than classical computers, but you cannot say they can do something useful better than classical computers. At present, “Quantum supremacy” only applies to toy problems. Your other question is not so easily answered.
- gobengo 4y ago
  > Can these computers actually do something better than their classical counterparts, right now? The answer is yes. Sometimes this is referred to as 'quantum supremacy' and some researchers at Google declared it in 2019. https://www.nature.com/articles/s41586-019-1666-5 https://www.nature.com/articles/s41586-019-1666-5 https://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html https://ai.googleblog.com/2019/10/quantum-supremacy-using-pr...
  - isoprophlex 4y ago
    Thanks, interesting idea but it seems the practical applicability is still far away. > One of the most celebrated results in quantum computing is the development of a quantum algorithm for factorization that works in time polynomial in n. This algorithm, due to Peter Shor and known as Shor’s algorithm, runs in O (n3 log n) time and uses O (n2 log n log log n) gates. The first experimental implementation of this algorithm on a quantum computer was reported in 2001, when the number 15 was factored. The largest integer factored by Shor’s algorithm so far is 21.
  - YakBizzarro 4y ago
    Quantum supremacy, while a very interesting experiment and a milestone in quantum computing, proves hardly anything about usefulness of quantum computers. It "only" proves that quantum computers are the best quantum computers, and classic ones can't efficiently simulate them. It say nothing about useful operations.
    - s1dev 4y ago
      From a theoretical point of view, this is evidence that quantum computing is a more powerful model of computation. I think it would be hard to argue that a model of computation that can solve more problems is any less useful. Applications like quantum simulation do appear to be difficult on a classical computer yet efficiently computable on a quantum computer
      - kbelder 4y ago
        Basketball is hard to simulate on a classical computer, but easy to simulate by playing a game of basketball.
dr_dshiv 4y ago
See the “Quantum Algorithm Zoo” for a comprehensive list of quantum algorithms. https://quantumalgorithmzoo.org/ https://quantumalgorithmzoo.org/ Massive amounts of work is needed to make these comprehensible.
- westurner 4y ago
  > Tequila is an Extensible Quantum Information and Learning Architecture where the main goal is to simplify and accelerate implementation of new ideas for quantum algorithms. It operates on abstract data structures allowing the formulation, combination, automatic differentiation and optimization of generalized objectives. Tequila can execute the underlying quantum expectation values on state of the art simulators as well as on real quantum devices. https://github.com/tequilahub/tequila#quantum-backends https://github.com/tequilahub/tequila#quantum-backends Quantum Backends currently supported by tequilahub/tequila: Qulacs, Qibo, Qiskit, Cirq (SymPy), PyQuil, QLM / myQLM tequila-tutorials/Quantum_Calculator.ipynb https://github.com/tequilahub/tequila-tutorials/blob/main/Quantum_Calculator.ipynb https://github.com/tequilahub/tequila-tutorials/blob/main/Qu... : > Welcome to the Tequila Calculator Tutorial. In this tutorial, you will learn how to create a quantum circuit that simulates addition using Tequila. We also compare the performance of various backends that Tequila uses.
  - westurner 4y ago
    A problem that could possibly be quantum-optimized and an existing set of solutions: Scheduling Optimize the scheduling problem better than e.g. SLURM and then generate a sufficient classical solution that executes in P-space on classical computers. SLURM https://en.wikipedia.org/wiki/Slurm_Workload_Manager https://en.wikipedia.org/wiki/Slurm_Workload_Manager : > Slurm uses a best fit algorithm based on Hilbert curve scheduling or fat tree network topology in order to optimize locality of task assignments on parallel computers.[2] Additional applications and use cases: "Employee Scheduling" > "Ask HN: What algorithms should I research to code a conference scheduling app" https://news.ycombinator.com/item?id=22589911 https://news.ycombinator.com/item?id=22589911 > [Hilbert Curve Scheduling] https://en.wikipedia.org/wiki/Hilbert_curve_scheduling https://en.wikipedia.org/wiki/Hilbert_curve_scheduling : > [...] the Hilbert curve scheduling method turns a multidimensional task allocation problem into a one-dimensional space filling problem using Hilbert curves, assigning related tasks to locations with higher levels of proximity.[1] Other space filling curves may also be used in various computing applications for similar purposes.[2]
rg111 4y ago
Also nice: Quantum Country: A Free Introduction to Quantum Computing and Quantum Mechanics [0][1][2] The content is okay (as far as I read), and it has Spaced Repeatition built-in. [0]: https://quantum.country/ https://quantum.country/ [1]: https://news.ycombinator.com/item?id=23561018 https://news.ycombinator.com/item?id=23561018 [2]: https://news.ycombinator.com/item?id=19426573 https://news.ycombinator.com/item?id=19426573
- 363849473754 4y ago
  I’ll copy paste what I wrote before about quantum country This doesn’t provide solutions to the problems and doesn’t show you how to do the mathematical calculations. It assumes you know proof based linear algebra and if you’re a math beginner the level that this is written at will be beyond you. Instead I recommend https://www.thomaswong.net/introduction-to-classical-and-quantum-computing-1e2p.pdf https://www.thomaswong.net/introduction-to-classical-and-qua... which doesn’t assume much pre-req knowledge and contains solutions so you can check your work
  - rg111 4y ago
    I did not know about this one. Thanks. As someone who went to do a Physics BS from a solid uni, I didn't find QC difficult (I didn't finish it, though.)
desmond373 4y ago
As someone who did most of IBMs quantum course, the difficulty didn't come with the generating code part. It came with the application. How do I use this to speed up database access? How do I use this to better commute graphics? Can you make a neural net better with this? Giving people useful applications will generate more interest than you will need.
- dr_dshiv 4y ago
  Useful applications don’t exist. They surely will, at some point, but not yet. That’s why they aren’t provided as examples.
  - jtc42 4y ago
    There are/seem to be very specific scientific applications, mostly around simulation of other systems whose hamiltonians map nicely to that of the computer. For almost everyone on the planet that isn’t very useful, but for that small handful it can be a game changer. … doesn’t contribute much here, but worth knowing! It’s exciting either way.
  - amelius 4y ago
    Protein folding (computational chemistry), and breaking everyone's crypto.
    - nabla9 4y ago
      > breaking everyone's crypto Symmetric encryption and hash functions with 256 bits are already quantum proof. Post-quantum algorithms are here in few years. Some of them are already in use in critical applications.
      - t_mann 4y ago
        Importantly, Bitcoin and Ethereum are (inadvertently) almost quantum-proof (because the addresses are hashes of the public keys), just not quite (because the public keys still get exposed during transactions). But at least the latter should be fixable (because the community is quite used to changes to the protocol anyway).
itvision 4y ago
Almost three dozen authors, yeah, for "beginners" :-)
- rg111 4y ago
  I guess different people just wrote different parts. I skimmed over some pages and the content did seem like it was for beginners.
reeboo 4y ago
"... are shorthands for the vectors encoding the two basis states of a two dimensional vector space." How many beginner's know what a basis of a vector space is -- how about unitary operators -- Eigen stuff? The word "beginner" does a disservice to the level you need to be at to start wadding into quantum stuff. At a minimum, you better not be a beginner of linear algebra! There is, imo, no better way to discourage people than saying this stuff is for "beginners".

110 points by rg111 4y ago

Unfortunately every page of the document has the words "Just accepted" across the whole page making it almost unreadable (as in: can be read, but it's painful)

ketanmaheshwari 4y ago
I have a copy without any watermarks. How should I share it here or share with you?
- __rito__ 4y ago
  Not GP, but, can you send me via email? Email on bio.
jcarreiro 4y ago
You can download a version without the watermarks from arXiv: https://arxiv.org/abs/1804.03719 https://arxiv.org/abs/1804.03719.

deleted 4y ago

[deleted]

isoprophlex 4y ago

Not trolling: is there really a need to train a cohort of quantum programmers? Can these computers actually do something better than their classical counterparts, right now?

samstave 4y ago
I, for one, welcome any learning. So even if I am never actually to program a quantum computer, Why would I not like to know how to do such? Why should the ability/knowledge be hidden from any body. But you'll never know, until you look at me.
- rusticpenn 4y ago
  You can program a quantum computer today, ibm quantum computing cloud provides all 5qubit computing for free.
  - dr_dshiv 4y ago
    Also see Quantum Inspire for free, accessible quantum computing on the cloud: https://www.quantum-inspire.com/ https://www.quantum-inspire.com/
dr_dshiv 4y ago
> Can these computers actually do something better than their classical counterparts, right now? You could say quantum computers do something better than classical computers, but you cannot say they can do something useful better than classical computers. At present, “Quantum supremacy” only applies to toy problems. Your other question is not so easily answered.
gobengo 4y ago
> Can these computers actually do something better than their classical counterparts, right now? The answer is yes. Sometimes this is referred to as 'quantum supremacy' and some researchers at Google declared it in 2019. https://www.nature.com/articles/s41586-019-1666-5 https://www.nature.com/articles/s41586-019-1666-5 https://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html https://ai.googleblog.com/2019/10/quantum-supremacy-using-pr...
- isoprophlex 4y ago
  Thanks, interesting idea but it seems the practical applicability is still far away. > One of the most celebrated results in quantum computing is the development of a quantum algorithm for factorization that works in time polynomial in n. This algorithm, due to Peter Shor and known as Shor’s algorithm, runs in O (n3 log n) time and uses O (n2 log n log log n) gates. The first experimental implementation of this algorithm on a quantum computer was reported in 2001, when the number 15 was factored. The largest integer factored by Shor’s algorithm so far is 21.
- YakBizzarro 4y ago
  Quantum supremacy, while a very interesting experiment and a milestone in quantum computing, proves hardly anything about usefulness of quantum computers. It "only" proves that quantum computers are the best quantum computers, and classic ones can't efficiently simulate them. It say nothing about useful operations.
  - s1dev 4y ago
    From a theoretical point of view, this is evidence that quantum computing is a more powerful model of computation. I think it would be hard to argue that a model of computation that can solve more problems is any less useful. Applications like quantum simulation do appear to be difficult on a classical computer yet efficiently computable on a quantum computer
    - kbelder 4y ago
      Basketball is hard to simulate on a classical computer, but easy to simulate by playing a game of basketball.

dr_dshiv 4y ago

See the “Quantum Algorithm Zoo” for a comprehensive list of quantum algorithms. https://quantumalgorithmzoo.org/ https://quantumalgorithmzoo.org/ Massive amounts of work is needed to make these comprehensible.

westurner 4y ago
> Tequila is an Extensible Quantum Information and Learning Architecture where the main goal is to simplify and accelerate implementation of new ideas for quantum algorithms. It operates on abstract data structures allowing the formulation, combination, automatic differentiation and optimization of generalized objectives. Tequila can execute the underlying quantum expectation values on state of the art simulators as well as on real quantum devices. https://github.com/tequilahub/tequila#quantum-backends https://github.com/tequilahub/tequila#quantum-backends Quantum Backends currently supported by tequilahub/tequila: Qulacs, Qibo, Qiskit, Cirq (SymPy), PyQuil, QLM / myQLM tequila-tutorials/Quantum_Calculator.ipynb https://github.com/tequilahub/tequila-tutorials/blob/main/Quantum_Calculator.ipynb https://github.com/tequilahub/tequila-tutorials/blob/main/Qu... : > Welcome to the Tequila Calculator Tutorial. In this tutorial, you will learn how to create a quantum circuit that simulates addition using Tequila. We also compare the performance of various backends that Tequila uses.
- westurner 4y ago
  A problem that could possibly be quantum-optimized and an existing set of solutions: Scheduling Optimize the scheduling problem better than e.g. SLURM and then generate a sufficient classical solution that executes in P-space on classical computers. SLURM https://en.wikipedia.org/wiki/Slurm_Workload_Manager https://en.wikipedia.org/wiki/Slurm_Workload_Manager : > Slurm uses a best fit algorithm based on Hilbert curve scheduling or fat tree network topology in order to optimize locality of task assignments on parallel computers.[2] Additional applications and use cases: "Employee Scheduling" > "Ask HN: What algorithms should I research to code a conference scheduling app" https://news.ycombinator.com/item?id=22589911 https://news.ycombinator.com/item?id=22589911 > [Hilbert Curve Scheduling] https://en.wikipedia.org/wiki/Hilbert_curve_scheduling https://en.wikipedia.org/wiki/Hilbert_curve_scheduling : > [...] the Hilbert curve scheduling method turns a multidimensional task allocation problem into a one-dimensional space filling problem using Hilbert curves, assigning related tasks to locations with higher levels of proximity.[1] Other space filling curves may also be used in various computing applications for similar purposes.[2]

rg111 4y ago

Also nice: Quantum Country: A Free Introduction to Quantum Computing and Quantum Mechanics [0][1][2] The content is okay (as far as I read), and it has Spaced Repeatition built-in. [0]: https://quantum.country/ https://quantum.country/ [1]: https://news.ycombinator.com/item?id=23561018 https://news.ycombinator.com/item?id=23561018 [2]: https://news.ycombinator.com/item?id=19426573 https://news.ycombinator.com/item?id=19426573

363849473754 4y ago
I’ll copy paste what I wrote before about quantum country This doesn’t provide solutions to the problems and doesn’t show you how to do the mathematical calculations. It assumes you know proof based linear algebra and if you’re a math beginner the level that this is written at will be beyond you. Instead I recommend https://www.thomaswong.net/introduction-to-classical-and-quantum-computing-1e2p.pdf https://www.thomaswong.net/introduction-to-classical-and-qua... which doesn’t assume much pre-req knowledge and contains solutions so you can check your work
- rg111 4y ago
  I did not know about this one. Thanks. As someone who went to do a Physics BS from a solid uni, I didn't find QC difficult (I didn't finish it, though.)

desmond373 4y ago

As someone who did most of IBMs quantum course, the difficulty didn't come with the generating code part. It came with the application. How do I use this to speed up database access? How do I use this to better commute graphics? Can you make a neural net better with this? Giving people useful applications will generate more interest than you will need.

dr_dshiv 4y ago
Useful applications don’t exist. They surely will, at some point, but not yet. That’s why they aren’t provided as examples.
- jtc42 4y ago
  There are/seem to be very specific scientific applications, mostly around simulation of other systems whose hamiltonians map nicely to that of the computer. For almost everyone on the planet that isn’t very useful, but for that small handful it can be a game changer. … doesn’t contribute much here, but worth knowing! It’s exciting either way.
- amelius 4y ago
  Protein folding (computational chemistry), and breaking everyone's crypto.
  - nabla9 4y ago
    > breaking everyone's crypto Symmetric encryption and hash functions with 256 bits are already quantum proof. Post-quantum algorithms are here in few years. Some of them are already in use in critical applications.
    - t_mann 4y ago
      Importantly, Bitcoin and Ethereum are (inadvertently) almost quantum-proof (because the addresses are hashes of the public keys), just not quite (because the public keys still get exposed during transactions). But at least the latter should be fixable (because the community is quite used to changes to the protocol anyway).

itvision 4y ago

Almost three dozen authors, yeah, for "beginners" :-)

rg111 4y ago
I guess different people just wrote different parts. I skimmed over some pages and the content did seem like it was for beginners.

reeboo 4y ago

"... are shorthands for the vectors encoding the two basis states of a two dimensional vector space." How many beginner's know what a basis of a vector space is -- how about unitary operators -- Eigen stuff? The word "beginner" does a disservice to the level you need to be at to start wadding into quantum stuff. At a minimum, you better not be a beginner of linear algebra! There is, imo, no better way to discourage people than saying this stuff is for "beginners".