Dynamic Programming

Optimal substructure means that the optimal solution can be constructed from optimal solutions of sub-problems. Think recursion. When we combine optimal solutions to non-overlapping sub-problems the algorithmic technique is called divide and conquer. Think of a merge sort where each sub-sort can happen independently and they are combined at the end. When we combine optimal solutions to overlapping sub-problems the algorithmic technique we can use is dynamic programming. Because the sub-problems overlap, we can improve the running time by remembering the results of already computed sub-problems and not computing them again.

An easy way to visualize this is in calculating Fibonacci numbers. The standard recursive solution can be memoized to significantly improve time complexity at the cost of using more space to store sub-problem results. This is top-down dynamic programming—recursion and memoization. Top-down dynamic programming can be easier to program and anecdotally it is more commonly used.

Bottom-up dynamic programming is instead iterative and we solve sub-problems first, building them into bigger sub-problems. Without the overhead of recursive calls we don't necessarily increase space complexity, but still have the decrease in time complexity. For calculating the nth Fibonacci number this looks like:

This is time complexity O(n) and space complexity O(1), a huge improvement on the naive recursive solution that's O(2ⁿ) time and O(n) space. For details on big-O of recursive algorithms read this.

Some other interesting applications of dynamic programming are:

• Dijkstra's algorithm (shortest paths)
• Tower of Hanoi (teaching game)
• Knapsack problem (combinatorial optimization)

The knapsack problem, for example, has a top-down solution but I think the bottom-up solution is especially appealing. Using a matrix to store sub-problem solutions we can make the O(2ⁿ) time recursive algorithm O(nW) time and space:

But wait, there's more. We only need to remember a part of the matrix for the next iteration, which means we don't even need the matrix. It can be further optimized to only use O(W) space:

Not, in my opinion, an obvious solution by any means, but a very elegant one.

Quantum Teleportation

I recently checked out the IBM Quantum Experience and was really impressed with the content available for getting started with quantum computing. There are simulators for executing quantum circuits, runnable both locally and in the cloud, but the highlight is being able to submit jobs to run on a real quantum computer. To create these circuits we use the Python DSL Qiskit.

For gaining a better understanding of Qiskit I recommend starting with the Coding with Qiskit video series. Following along with the videos and coding my first circuit then led down a rabbit hole of trying to understand what I was really building and how it could be useful.

Quantum computing uses phenomena from quantum mechanics like superposition and entanglement to perform computation. In classical computing we have bits which can either be on or off, 1 or 0. In quantum computing we have qubits which can be on or off at the same time, or somewhere in between. This is superposition. I like the coin analogy from Quantum computers will change the world (if they work) of this being a coin flip (classical) versus a spinning coin (quantum).

A qubit is represented as a vector of two complex numbers with length 1 where these represent the probability of a 0 or 1 state. Measurements destroy quantum state, collapsing the qubit to a classical bit. A measurement cannot be reversed. A quantum state cannot be copied like a classical bit's state can. Instead, quantum teleportation is the transfer of state from one qubit to another via a linkage known as entanglement. Even if moved far apart, entangled particles transmit information to one another. One coin flip mirroring another, linked flip.

The probabilistic nature of quantum computing enables many calculations to be processed simultaneously, thus making some intractable problems tractable. Quantum algorithms use superposition or entanglement to solve problems like factorization or search faster than classical algorithms. Qiskit has some amazing Jupyter notebooks showing how these can be used. Three I thought looked the most interesting, for example:

• quantum-enhanced support vector machines
• traveling salesman problem
• portfolio diversification

My first circuit is much simpler, of course, but I feel good about getting it running. Based on the videos linked above, I teleport a 1 state from one qubit to another and then measure it to confirm. I simulate this locally, in the cloud, and then run it on one of IBM's quantum computers. The actual quantum computer run includes some noise which is from the imperfect nature of today's quantum computers.

UPDATE:

TensorFlow Quantum is another library that could be used if you want to leverage Google's quantum computing resources.