Quantum annealers like those from D-Wave Systems implement adiabatic quantum computing to solve optimization problems, but their analog nature and limited control functionalities present challenges to correcting or mitigating errors. As quantum computing advances towards applications, effective error suppression is an important research goal. We propose a new approach called replication based mitigation (RBM) based on parallel quantum annealing. In RBM, physical qubits representing the same logical qubit are dispersed across different copies of the problem embedded in the hardware. This mitigates hardware biases, is compatible with limited qubit connectivity in current annealers, and is suited for available noisy intermediate-scale quantum (NISQ) annealers. Our experimental analysis shows that RBM provides solution quality on par with previous methods while being compatible with a much wider range of hardware connectivity patterns. In comparisons against standard quantum annealing without error mitigation, RBM consistently improves the energies and ground state probabilities across parameterized problem sets.

With the boom in the development of computer hardware and software, social media, IoT platforms, and communications, there has been exponential growth in the volume of data produced worldwide. Among these data, relational datasets are growing in popularity as they provide unique insights regarding the evolution of communities and their interactions. Relational datasets are naturally non-negative, sparse, and extra-large. Relational data usually contain triples (subject, relation, object) and are represented as graphs/multigraphs, called knowledge graphs, which need to be embedded into a low-dimensional dense vector space. Among various embedding models, RESCAL allows the learning of relational data to extract the posterior distributions over the latent variables and to make predictions of missing relations. However, RESCAL is computationally demanding and requires a fast and distributed implementation to analyze extra-large real-world datasets. Here we introduce a distributed non-negative RESCAL algorithm for heterogeneous CPU/GPU architectures with automatic selection of the number of latent communities (model selection), called pyDRESCALk. We demonstrate the correctness of pyDRESCALk with real-world and large synthetic tensors and the efficacy showing near-linear scaling that concurs with the theoretical complexities. Finally, pyDRESCALk determines the number of latent communities in an 11-terabyte dense and 9-exabyte sparse synthetic tensor.

A central challenge in protein modeling research and protein structure prediction in particular is known as decoy selection. The problem refers to selecting biologically-active/native tertiary structures among a multitude of physically-realistic structures generated by template-free protein structure prediction methods. Research on decoy selection is active. Clustering-based methods are popular, but they fail to identify good/near-native decoys on datasets where near-native decoys are severely under-sampled by a protein structure prediction method. Reasonable progress is reported by methods that additionally take into account the internal energy of a structure and employ it to identify basins in the energy landscape organizing the multitude of decoys. These methods, however, incur significant time costs for extracting basins from the landscape. In this paper, we propose a novel decoy selection method based on non-negative matrix factorization. We demonstrate that our method outperforms energy landscape-based methods. In particular, the proposed method addresses both the time cost issue and the challenge of identifying good decoys in a sparse dataset, successfully recognizing near-native decoys for both easy and hard protein targets.

To solve an optimization problem using a commercial quantum annealer, one has to represent the problem of interest as an Ising or a quadratic unconstrained binary optimization (QUBO) problem and submit its coefficients to the annealer, which then returns a user-specified number of low-energy solutions. It would be useful to know what happens in the quantum processor during the anneal process so that one could design better algorithms or suggest improvements to the hardware. However, existing quantum annealers are not able to directly extract such information from the processor. Hence, in this article we propose to use advanced features of D-Wave 2000Q to indirectly infer information about the dynamics of the state evolution during the anneal process. Specifically, D-Wave 2000Q allows the user to customize the anneal schedule, that is, the schedule with which the anneal fraction is changed from the start to the end of the anneal. Using this feature, we design a set of modified anneal schedules whose outputs can be used to generate information about the states of the system at user-defined time points during a standard anneal. With this process, called slicing , we obtain approximate distributions of lowest-energy anneal solutions as the anneal time evolves. We use our technique to obtain a variety of insights into the annealer, such as the state evolution during annealing, when individual bits in an evolving solution flip during the anneal process and when they stabilize, and we introduce a technique to estimate the freeze-out point of both the system as well as of individual qubits.

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.

Quantum annealers offer an efficient way to compute high quality solutions of NP-hard problems when expressed in a QUBO (quadratic unconstrained binary optimization) or an Ising form. This is done by mapping a problem onto the physical qubits and couplers of the quantum chip, from which a solution is read after a process called quantum annealing. However, this process is subject to multiple sources of biases, including poor calibration, leakage between adjacent qubits, control biases, etc., which might negatively influence the quality of the annealing results. In this work, we aim at mitigating the effect of such biases for solving constrained optimization problems, by offering a two-step method, and apply it to Graph Partitioning. In the first step, we measure and reduce any biases that result from implementing the constraints of the problem. In the second, we add the objective function to the resulting bias-corrected implementation of the constraints, and send the problem to the quantum annealer. We apply this concept to Graph Partitioning, an important NP-hard problem, which asks to find a partition of the vertices of a graph that is balanced (the constraint) and minimizes the cut size (the objective). We first quantify the bias of the implementation of the constraint on the quantum annealer, that is, we require, in an unbiased implementation, that any two vertices have the same likelihood of being assigned to the same or to different parts of the partition. We then propose an iterative method to correct any such biases. We demonstrate that, after adding the objective, solving the resulting bias-corrected Ising problem on the quantum annealer results in a higher solution accuracy.

The so-called dark proteome, referring to regions of the protein universe that remain inaccessible by either wet-or dry-laboratory methods, continues to spur computational research in protein structure determination. An outstanding challenge relates to the ability to discriminate relevant tertiary structure(s) among many structures, also referred to as decoys, that are computed for a protein of interest. The problem is known as decoy selection. While prime for investigation as an inference problem, the decoy datasets generated in silico are sparse and highly imbalanced towards the negative class (irrelevant structures). These characteristics continue to challenge both supervised and unsupervised learning approaches to this problem. In this paper, we propose a novel decoy selection method based on symmetric non-negative matrix factorization in a graph clustering setting. The method is evaluated on two datasets, a benchmark dataset of ensembles of decoys for a varied list of protein molecules, and a dataset of decoy ensembles for targets drawn from the recent CASP competitions. The evaluation demonstrates that the proposed method outperforms several state-of-the-art decoy selection methods. This performance, as well as the method's computational expediency, suggest that the proposed method advances the state of the art in decoy selection and, in particular, our the ability to tackle inherent challenges related to imbalanced datasets.

Quantum annealing computers are designed to produce high-quality solutions to optimization problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. While most of the well known NP-hard problems can easily be represented as quadratic binary problems, such formulations usually contain constraints that have to be added as penalties to the objective function in order to obtain QUBOs. In this paper, we propose a method based on finite automaton representation of the constraints for generating penalty implementations for them, which uses fewer qubits than the alternatives and is general enough to be applied to a whole class of constraints.

Non-negative Matrix Factorization (NMF) models the topics of a text corpus by decomposing the matrix of term frequency-inverse document frequency (TF-IDF) representation, X, into two low-rank non-negative matrices: W , representing the topics and H, mapping the documents onto space of topics. One challenge, common to all topic models, is the determination of the number of latent topics (aka model determination). Determining the correct number of topics is important: underestimating the number of topics results in a poor topic separation, under-fitting, while overestimating leads to noisy topics, over-fitting. Here, we introduce SeNMFk, a semantic-assisted NMF-based topic modeling method, which incorporates semantic correlations in NMF by using a word-context matrix, and employs a method for determination of the number of latent topics. SeNMFk first creates a random ensemble of matrices based on the initial TF-IDF matrix and a word-context matrix, and then applies a coupled factorization to acquire sets of stable coherent topics that are robust to noise. The latent dimension is determined based on the stability of these topics. We show that SeNMFk accurately determines the number of high-quality topics in benchmark text corpora, which leads to an accurate document clustering.

We propose an optimization approach for determining both hardware and software parameters for the efficient implementation of a (family of) applications called dense stencil computations on programmable general purpose computing on graphics processing units. We first introduce a simple, analytical model for the silicon area usage of accelerator architectures and a workload characterization of stencil computations. We combine this characterization with a parametric execution-time model and formulate a mathematical optimization problem that seeks to maximize a common objective function of all the hardware and software parameters. The solution to this problem, therefore, “solves” the codesign problem: simultaneously choosing software-hardware parameters to optimize total performance. We validate this approach by proposing architectural variants of the NVIDIA Maxwell GTX-980 (respectively, Titan X) specifically tuned to a predetermined workload of four common 2-D stencils (Heat, Jacobi, Laplacian, and Gradient) and two 3-D ones (Heat and Laplacian). Our model predicts that performance would potentially improve by 28% (respectively, 33%) with simple tweaks to the hardware parameters, such as tuning the number of streaming multiprocessors, the number of compute cores each contains, and the size of shared memory. We also develop a number of insights about the optimal regions of the design landscape.

Identifying biologically-active protein structure(s) from an ensemble of computed three-dimensional structures is a major challenge. Clustering-based methods are time-consuming and often under perform on structure datasets that are highly imbalanced. Energy landscape-based methods improve performance over imbalanced datasets but incur significant time costs. In this paper we propose a novel method based on non-negative matrix factorization. The method outperforms energy landscape-based clustering methods, addressing both time costs and challenges with imbalanced structure datasets.

We consider the minimum vertex cover problem having applications in e.g. biochemistry and network security. Quantum annealers can find the optimum solution of such NP-hard problems, given they can be embedded on the hardware. This is often infeasible due to limitations of the hardware connectivity structure. This paper presents a decomposition algorithm for the minimum vertex cover problem: The algorithm recursively divides an arbitrary problem until the generated subproblems can be embedded and solved on the annealer. To speed up the decomposition, we propose several pruning and reduction techniques. The performance of our algorithm is assessed in a simulation study.

Commercial adiabatic quantum annealers have the potential to solve important NP-hard optimization problems efficiently. The newest generation of those machines additionally allows the user to customize the anneal schedule, that is, the schedule with which the anneal fraction is changed from the start to the end of the annealing. In this work we use the aforementioned feature of the D-Wave 2000Q to attempt to monitor how the anneal solution evolves during the anneal process. This process we call slicing: at each time slice during the anneal, we are able to obtain an approximate distribution of anneal solutions. We use our technique to obtain a variety of insights into the D-Wave 2000Q. For example, we observe when individual bits flip during the anneal process and when they stabilize, which allows us to determine the freeze-out point for each qubit individually. We highlight our results using both random QUBO (quadratic unconstrained binary optimization) instances and, for better visualization, instances which we specifically optimize (using our own genetic algorithm) to exhibit a pronounced evolution of its solution during the anneal.

Stencil computations are an important class of compute and data intensive programs that occur widely in scientific and engineeringapplications. A number of tools use sophisticated tiling, parallelization, and memory mapping strategies, and generate code that relies on vendor-supplied compilers. This code has a number of parameters, such as tile sizes, that are then tuned via empirical exploration.

We describe a new algorithm for solving the all-pairs shortest-path (APSP) problem for planar graphs and graphs with small separators that exploits the massive on-chip parallelism available in today's Graphics Processing Units (GPUs). Our algorithm, based on the Floyd-War shall algorithm, has near optimal complexity in terms of the total number of operations, while its matrix-based structure is regular enough to allow for efficient parallel implementation on the GPUs. By applying a divide-and-conquer approach, we are able to make use of multi-node GPU clusters, resulting in more than an order of magnitude speedup over the fastest known Dijkstra-based GPU implementation and a two-fold speedup over a parallel Dijkstra-based CPU implementation.

One of the most useful measures of cluster quality is the modularity of the partition, which measures the difference between the number of the edges joining vertices from the same cluster and the expected number of such edges in a random graph. In this paper, we show that the problem of finding a partition maximizing the modularity of a given graph G can be reduced to a minimum weighted cut (MWC) problem on a complete graph with the same vertices as G. We then show that the resulting minimum cut problem can be efficiently solved by adapting existing graph partitioning techniques. Our algorithm finds clusterings of a comparable quality and is much faster than the existing clustering algorithms.

The girth of a graph G is the length of a shortest cycle of G . In this article we design an O ( n 5/4 log n ) algorithm for finding the girth of an undirected n -vertex planar graph, the first o ( n 2 ) algorithm for this problem. We also extend our results for the class of graphs embedded into an orientable surface of small genus. Our approach uses several techniques such as graph partitioning, hammock decomposition, graph covering, and dynamic shortest-path computation. We discuss extensions and generalizations of our result.

The exposure of a path p in a sensor field is a measure of the likelihood that an object traveling along p is detected by at least one sensor from a network of sensors, and is formally defined as an integral over all points x of p of the sensibility (the strength of the signal coming from x ) times the element of path length. The minimum exposure path (MEP) problem is, given a pair of points x and y inside a sensor field, to find a path between x and y of minimum exposure. In this article we introduce the first rigorous treatment of the problem, designing an approximation algorithm for the MEP problem with guaranteed performance characteristics. Given a convex polygon P of size n with O(n) sensors inside it and any real number ϵ>0, our algorithm finds a path in P whose exposure is within an 1+ϵ factor of the exposure of the MEP, in time O ( n /ϵ 2 ψlog n ), where ψ is a geometric characteristic of the field. We also describe a framework for a faster implementation of our algorithm, which reduces the time by a factor of approximately θ(1/ϵ), while keeping the same approximation ratio.

We construct an optimal linear-time algorithm for the maximal planar subgraph problem: given a graph G, find a planar subgraph G' of G such that adding to G' an extra edge of G results in a nonplanar graph. Our solution is based on a fast data structure for incremental planarity testing of triconnected graphs and a dynamic graph search procedure. Our algorithm can be transformed into a new optimal planarity testing algorithm.

This paper develops new techniques for constructing separators for graphs embedded on surfaces of bounded genus. For any arbitrarily small positive $\varepsilon $ we show that any n-vertex graph G of genus g can be divided in $O(n + g)$ time into components whose sizes do not exceed $\varepsilon n$ by removing a set C of $O(\sqrt {(g + 1/\varepsilon )} n)$ vertices. Our result improves the best previous ones with respect to the size of C and the time complexity of the algorithm. Moreover, we show that one can cut off from G a piece of no more than $(1 - \varepsilon )n$ vertices by removing a set of $O(\sqrt {n\varepsilon (g\varepsilon + 1)} )$ vertices. Both results are optimal up to a constant factor.

We give an algorithm for imbedding a graph G of n vertices onto an oriented surface of minimal genus g. If g> 0 then we also construct a forbidden subgraph of G which is homeomorphic to a graph of size exp(O(g)!) which cannot be imbedded on a surface of genus g-1. Our algorithm takes sequential time exp(O(g)!)nO(1). Since exp(O(g)!) = exp(exp(O(glog(g)))), our algorithm is polynomial time for genus g=O(loglog(n)/logloglog(n)). A simple parallel implementation of our algorithm takes parallel time (logn) O(1) +O(g)! using exp(O(g)!)nO(1) processors. We give also the smallest known upper bound, namely exp(O(g)!), on the number F(g) of homeomorphic distinct forbidden subgraphs for graph imbeddings onto a surface of genus g. The two best previous algorithms [Filotti, Miller, Reif,79] and [Robertson and Seymour,86] for graph imbedding onto a surface of genus g, required nO(g) and f(g)n2 sequential time, respectively. The work of [Robertson and Seymour,86] also gave a finite bound for F(g). However their proof spanned many papers and were highly nonconstructive; f(g) and F(g) were bounded by some (large) tower of exponents of g. Our work provides a distinct constructive approach giving considerably improved bounds for f(g)