Ciro Santilli @cirosantilli  40

This is the true key question: what are the most important algorithms that would be accelerated by quantum computing?

Some candidates:

Do you have proper optimization or quantum chemistry algorithms that will make trillions?

Maybe there is some room for doubt because some applications might be way better in some implementations, but we should at least have a good general idea.

However, clear information on this really hard to come by, not sure why.

Whenever asked e.g. at: physics.stackexchange.com/questions/3390/can-anybody-provide-a-simple-example-of-a-quantum-computer-algorithm/3407 on Physics Stack Exchange people say the infinite mantra:

Lists:

Software that maps higher level languages like Qiskit into actual quantum circuits.

It is hard to beat the list present at Quantum computing report: quantumcomputingreport.com/players/.

The much less-complete Wikipedia page is also of interest: en.wikipedia.org/wiki/List_of_companies_involved_in_quantum_computing_or_communication It has the merit of having a few extra columns compared to Quantum computing report.

Also of interest: quantumzeitgeist.com/interactive-map-of-quantum-computing-companies-from-around-the-globe/

Based on the Josephson effect. Yet another application of that phenomenal phenomena!

Philosophically, superconducting qubits are good because superconductivity is macroscopic.

It is fun to see that the representation of information in the QC basically uses an LC circuit, which is a very classical resonator circuit.

As mentioned at en.wikipedia.org/wiki/Superconducting_quantum_computing#Qubit_archetypes there are actually a few different types of superconducting qubits:

and hybridizations of those such as:

Input:

Other good lists:

Bibliography:

In the context of quantum computing of the 2020's, a "classical computer" is a computer that is not "quantum", i.e., the then dominating CMOS computers.

As en.wikipedia.org/w/index.php?title=ZX-calculus&oldid=1071329204#Diagram_rewriting tries to explain but fails to deliver as usual consider the GHZ state represented as a quantum circuit.

How can we easily prove that that quantum circuit equals the state:?

The naive way would be to just do the matrix multiplication as explained at Section "Quantum computing is just matrix multiplication".

However, ZX-calculus provides a simpler way.

And even more importantly, sometimes it is the only way, because in a real circuit, we would not be able to do the matrix multiplication

What we do in ZX-calculus is we first transform the original quantum circuit into a ZX graph.

This is always possible, because we can describe how to do the conversion simply for any of the Clifford plus T gates, which is a set of universal quantum gates.

Then, after we do this transformation, we can start applying further transformations that simplify the circuit.

It has already been proven that there is no efficient algorithm for this (TODO source, someone said P-sharp complete best case)

But it has been proven in 2017 that any possible equivalence between quantum circuits can be reached by modifying ZX-calculus circuits.

There are only 7 transformation rules that we need, and all others can be derived from those, universality.

So, we can apply those rules to do the transformation shown in Wikipedia:

and one of those rules finally tells us that that last graph means our desired state:because it is a Z spider with $m=3$ and $n=1$.

Bibliography:

At Section "Quantum computing is just matrix multiplication" we saw that making a quantum circuit actually comes down to designing one big unitary matrix.

We have to say though that that was a bit of a lie.

Quantum programmers normally don't just produce those big matrices manually from scratch.

Instead, they use quantum logic gates.

The following are the main reasons for that:

A quantum circuit is a graph of quantum logic gates.

Quantum circuits are the prevailing model of quantum computing as of the 2010's - 2020's

One important area of research and development of quantum computing is the development of benchmarks that allow us to compare different quantum computers to decide which one is more powerful than the other.

Ideally, we would like to be able to have a single number that predicts which computer is more powerful than the other for a wide range of algorithms.

However, much like in CPU benchmarking, this is a very complex problem, since different algorithms might perform differently in different architectures, making it very hard to sum up the architecture's capabilities to a single number as we would like.

The only thing that is directly comparable across computers is how two machines perform for a single algorithm, but we want a single number that is representative of many algorithms.

For example, the number of qubits would be a simple naive choice of such performance predictor number. But it is very imprecise, since other factors are also very important:

Quantum volume is another less naive attempt at such metric.

Encryption algorithms that run on classical computers that are expected to be resistant to quantum computers.

This is notably not the case of the dominant 2020 algorithms, RSA and elliptic curve cryptography, which are provably broken by Grover's algorithm.

However, as of 2020, we don't have any proof that any symmetric or public key algorithm is quantum resistant.

Post-quantum cryptography is the very first quantum computing thing at which people have to put money into.

The reason is that attackers would be able to store captured ciphertext, and then retroactively break them once and if quantum computing power becomes available in the future.

There isn't a shade of a doubt that intelligence agencies are actively doing this as of 2020. They must have a database of how interesting a given source is, and then store as much as they can given some ammount of storage budget they have available.

A good way to explain this to quantum computing skeptics is to ask them:Post-quantum cryptography is simply not a choice. It must be done now. Even if the risk is low, the cost would be way too great.