Quantum Algorithm Implementations for Beginners
dl.acm.org
dl.acm.org
Giving people useful applications will generate more interest than you will need.
… doesn’t contribute much here, but worth knowing! It’s exciting either way.
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.
It seems that you have missed some of the basics of quantum computing.
For quantum computing to work the system must be isolated from the environment for the period of the computation. You can't use it for anything interactive like graphics.
Any practical problem worth solving with quantum computer needs something like years or millions of years to solve using classical computer. Do you have database index where search takes years or graphics problem where output takes years?
Also consider the amount of qbits needed. For database search you need quantum computer with same order of magnitude qbits as the database index.
Practical problems for quantum computing are mostly scientific problems like simulating chemistry.
So for example, in computer science we can explain basic data structures like binary trees and hash tables from whichever context a student understands. We can use pointers and references from C-style imperative languages. We can use car and cdr from Lisp-style functional languages. We can even jump up to higher levels of abstraction with associative arrays in Javascript. Or make the whole thing in key-value stores like Redis or even a SQL database or x86 assembly if that floats our boat.
But with QC, even its "assembly language" of Hilbert spaces and tensors is already so difficult to understand, much less apply, that the terminology feels like gatekeeping. There's no way to easily identify the smoking gun(s) which separate a QC simulation from qubits in the real world. It's like asking an assembly language teacher how a full adder works, but they throw up their hands and say that first we must understand Fermi levels and electron diffusion across a PN junction. Which while important, doesn't answer the student's question.
What's needed are simple transforms to go from any existing formula/algorithm to its "optimized" QC equivalent. I don't know if that can be done in a general way, like how we can switch from the time domain to the frequency domain with a Fourier transform, or take the derivative of an equation. Maybe it's more like an integral where the solution must be "found" by composing known integrals from a dictionary using heuristics.
But without those transforms, I see us being stuck in a QC winter for the foreseeable future. My words are imperfect, but I know precisely what I'm getting at here. I can't run with QC the way I would with any other programming language, and it really bothers me. To the point of, I'll probably have to actually learn it from first principles and write it up from a programmer's perspective! Someday.
Debugging sounds like a real bear.
https://quantumalgorithmzoo.org/
Massive amounts of work is needed to make these comprehensible.
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/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.
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 :
> 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
> [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]
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.
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-qua...
which doesn’t assume much pre-req knowledge and contains solutions so you can check your work
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.)
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".
But you'll never know, until you look at me.
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.
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://ai.googleblog.com/2019/10/quantum-supremacy-using-pr...
> 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.
The only thing it can do faster is to run itself.
It's as if I called a Boeing airliner an aerodynamic computer and each flight a computaion.
In any test flight there are plenty of parameters set for the flight. Are aerodynamic computers programmable?
But in any case, the mere existence of "quantum supremacy" research is a clear indication these are pointless contraptions.
The second half of the article I shared covers the parametrization question you raised.
A successful technology does not need to show theoretical supremacy. Its proponents can simply show the useful services and products it makes.
> Proof of concepts that can not solve "useful" problems seem like an incredibly important milestones to me?
Sure, just don't claim supremacy until you can back it up with an actually reasonable definition of computation.
> Or is your frustration that they are occasionally presented by overly enthusiastic engineers as more than "useless" technology demonstrators (with this frustration I would agree).
It is hard to find any news about quantum computing that is not way over exaggerated.
> The second half of the article I shared covers the parametrization question you raised.
His argument may apply to the teapot example, but for, say, a test flight to fine tune the auto pilot behavior, there are plenty of inputs that can be set. I'd argue the aerodynamic computer supremacy example still stands.
In your first paragraph, while I am sympathetic with your annoyance (pardon my imprecise choice of words), I disagree there too. Mostly because I can imagine the same argument used against Babbage, Lovelace, and Turing, who did their theory (and failed experiment) work decades to a century before a scalable classical computer existed.
Email on bio.
I skimmed over some pages and the content did seem like it was for beginners.