As quantum computers become available to the general public, the need has arisen to train a cohort of quantum programmers, many of whom have been developing classical computer programs for most of their careers. While currently available quantum computers have less than 100 qubits, quantum computing hardware is widely expected to grow in terms of qubit count, quality, and connectivity. This review aims at explaining the principles of quantum programming, which are quite different from classical programming, with straightforward algebra that makes understanding of the underlying fascinating quantum mechanical principles optional. We give an introduction to quantum computing algorithms and their implementation on real quantum hardware. We survey 20 different quantum algorithms, attempting to describe each in a succinct and self-contained fashion. We show how these algorithms can be implemented on IBM’s quantum computer, and in each case, we discuss the results of the implementation with respect to differences between the simulator and the actual hardware runs. This article introduces computer scientists, physicists, and engineers to quantum algorithms and provides a blueprint for their implementations.

Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the post Moore’s law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets directly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this article, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. To demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Wave’s quantum annealer and IBM’s gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitude larger than the current quantum hardware size, and we observe results comparable to state-of-the-art solvers in terms of quality of the solution. Reproducibility : Our code and data are available at Reference [1].

We describe the various aspects involved in building FastTrans, a scalable, parallel microsimulator for transportation networks that can simulate and route tens of millions of vehicles on real-world road networks in a fraction of real time. Vehicular trips are generated using agent-based simulations that provide realistic, daily activity schedules for a synthetic population of millions of intelligent agents. We use parallel discrete-event simulation techniques and distributed-memory algorithms to scale these simulations to over one thousand compute nodes. We present various optimizations for speeding up simulation execution times, including (i) a set of routing algorithms such as variations of Dijkstra's shortest path algorithm and heuristic-based A* search, and (ii) a number of different partitioning schemes for load balancing, including geographic partitioning (that assigns simulation entities that are geographically close by to the same processor) and scattering (that assigns geographically close by entities to different processors). Our main findings include: (i) A* significantly outperforms other routing algorithms while computing near-optimal paths; (ii) surprisingly, scattering outperforms more sophisticated partitioning schemes by achieving near-perfect load-balancing. With optimized routing and partitioning, FastTrans is able to simulate a full 24 hour work-day in New York - involving over one million road links and approximately 25 million vehicular trips - in less than one hour of wall-clock time on a 512-node cluster.

BACKGROUND: We participated in the BioCreAtIvE Task 2, which addressed the annotation of proteins into the Gene Ontology (GO) based on the text of a given document and the selection of evidence text from the document justifying that annotation. We approached the task utilizing several combinations of two distinct methods: an unsupervised algorithm for expanding words associated with GO nodes, and an annotation methodology which treats annotation as categorization of terms from a protein's document neighborhood into the GO. RESULTS: The evaluation results indicate that the method for expanding words associated with GO nodes is quite powerful; we were able to successfully select appropriate evidence text for a given annotation in 38% of Task 2.1 queries by building on this method. The term categorization methodology achieved a precision of 16% for annotation within the correct extended family in Task 2.2, though we show through subsequent analysis that this can be improved with a different parameter setting. Our architecture proved not to be very successful on the evidence text component of the task, in the configuration used to generate the submitted results. CONCLUSION: The initial results show promise for both of the methods we explored, and we are planning to integrate the methods more closely to achieve better results overall.

The authors discuss problems and solutions pertaining to the interaction of components representing parallel applications. We introduce the notion of a collective port which is an extension of the Common Component Architecture (CCA) ports and allows collective components representing parallel applications to interact as one entity. We further describe a class of translation components, which translate between the distributed data format used by one parallel implementation to that used by another. A well known example of such components is the MxN component which translates between data distributed on M processors to data distributed on N processors. We describe its implementation in Parallel Application Work Space (PAWS), as well as the data structures PAWS uses to support it. We also present a mechanism allowing the framework to invoke this component on the programmer's behalf whenever such translation is necessary, freeing the programmer from treating collective component interactions as a special case. In doing that, we introduce framework-based, user-defined distributed type casts. Finally, we discuss our initial experiments in building optimized complex translation components out of atomic functionalities.

PAWS (Parallel Application WorkSpace) is a software infrastructure for use in connecting separate parallel applications within a component-like model. A central PAWS Controller coordinates the linking of serial or parallel applications across a network to allow them to share parallel data structures such as multidimensional arrays. Applications use the PAWS API to indicate which data structures are to be shared and at what points the data is ready to be sent or received. PAWS implements a general parallel data descriptor and automatically carries out parallel layout remapping when necessary. Connections can be dynamically established and dropped, and can use multiple data transfer pathways between applications. PAWS uses the NEXUS communication library and is independent of the application's parallel communication mechanism.

The authors study the principles governing the power and efficiency of the default hierarchy, a system of knowledge acquisition and representation. The default hierarchy trains automatically, yet yields a set of rules which can be easily assessed and analyzed. Rules are organized in a hierarchical structure containing general (default) and specific rules. In training the hierarchy, general rules are learned before specific rules. In using the hierarchy, specific rules are accessed first, with default rules used when no specific rules apply. The main results concern the properties of the default hierarchy architecture, as revealed by its application to English pronunciation. Evaluating the hierarchy as a pronouncer of English, the authors find that its rules capture several key features of English spelling. The default hierarchy pronounces English better than the neural network NETtalk, and almost as well as expert-devised systems.>