Quantum computing exploits quantum-mechanical effects—in particular superposition, entanglement, and quantum tunneling—to more efficiently execute a computation. Compared to traditional,digital computing, quantum computing offers the potential to dramatically reduce both executiontime and energy consumption. These potential advantages, steady advances in nano-manufacturing,and the slow-down of traditional hardware scaling laws (such as Moore’s Law) have led to a substantial commercial and national-security interest and investment in quantum computing technologyin the 2010s. Recently, Google announced that it has reached a major milestone known as quantum supremacy–the demonstration that a quantum computer can perform a calculation that isintractable on a classical supercomputer [9]. The problem tackled here by the quantum computeris not one with any direct real-world application. Nonetheless, this is a watershed moment forquantum computing and is widely seen as an important step on the road towards building quantumcomputers that will offer practical speedups when solving real-world problems [100]. (See [3] for aprecise technical definition of quantum supremacy.)
11.2 Algorithm description The Quantum algorithm described by Ambainis and Spalek is a quantized version of the EdmondsKarp algorithm, that is, the classical algorithm with quantum acceleration. The key quantum component is a generalized version of Grovers search algorithm that finds items in an unsorted list of length . The algorithm is used in creating a layered subgraph data structure that is subsequently used to find the shortest augmenting path at a given iteration. Like in Section XI, we will be oblivious to the number of marked items Grovers algorithm is searching for. So once again we have to use techniques from Ref. while performing the search.
id: be2ee8c3bba748b3026c550892d2c770 - page: 52
Here we will describe how to build a layered graph partition. In a layered graph partition each vertex in the graph is assigned to thew -th layer such that edges of the graph only connect between -th and ( + 1)-th layers. The key to quantization lies in using Grovers search to build a layered graph partition by computing layer numbers for all vertices. The layers are represented by an array L indexing the vertices of the graph, and assigning to each element a subgraph layer number. The sink vertex at vertex zero is set to zero. The the algorithm proceeds according to the following pseudo-code described in Algorithm 11. Algorithm 11 Layered graph partitioning Input: Adjacency information of the graph (Adjacency matrix, list of edges,etc.) Source vertex . Output: L such that L [] is the layer number of the -th vertex.
id: 4edefa53dbb58da955fe82aa27a4326b - page: 52
Procedure: Step 1. Set L [] = 0 and L [] = for 0 Step 2. Create a one-entry queue = {} while do ( = 0) Step 3a. Take the first vertex from . Step 3b. Find by Grover search all its neighbors with L [] = . Step 3c. Set L () = L [] + 1, append into , and remove from end while
id: d98b32c3b58fb80791ca29beed69cb3f - page: 52
Quantum Algorithm Implementations for Beginners Notice that the oracle for Grover search required for this algorithm is one that marks all the neighbours of whose layer number is currently set to . Grovers search speeds up the layers assignment of the vertices by quickly finding all the entries in the layer array L that contain the value . In practical terms, might simply be the largest value reachable in an n-qubit machine. The generalized Grover search would look for all such values without a priori knowing the number of such values. The size of a circuit required to do a full layered graph partitioning makes it impractical to implement it on the IBM machine. But the heart of the algorithm is Grover search, which we have already implemented earlier.
id: 5ba454e6023b6df9cc5e6ba00b2cb440 - page: 53