Synergies Between Operations Research and Quantum Information Science
This article highlights synergies between quantum information science (QIS) and operations research for QIS-curious operations researchers (and vice-versa).
Source author record
Ojas Parekh
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
9works
9topics
4close collaborators
Published work
9 publications
preprint2021arXiv
An explicit vector algorithm for high-girth MaxCut
We give an approximation algorithm for MaxCut and provide guarantees on the average fraction of edges cut on d-regular graphs of girth ≥2k. For every d≥3 and k≥4, our approximation guarantees are better than those of all other classical and quantum algorithms known to the authors. Our algorithm constructs an explicit vector solution to the standard semidefinite relaxation of MaxCut and applies hyperplane rounding. It may be viewed as a simplification of the previously best known technique, which approximates Gaussian wave processes on the infinite d-regular tree.
Open access
preprint2021arXiv
Neuromorphic scaling advantages for energy-efficient random walk computation
Computing stands to be radically improved by neuromorphic computing (NMC) approaches inspired by the brain's incredible efficiency and capabilities. Most NMC research, which aims to replicate the brain's computational structure and architecture in man-made hardware, has focused on artificial intelligence; however, less explored is whether this brain-inspired hardware can provide value beyond cognitive tasks. We demonstrate that high-degree parallelism and configurability of spiking neuromorphic architectures makes them well-suited to implement random walks via discrete time Markov chains. Such random walks are useful in Monte Carlo methods, which represent a fundamental computational tool for solving a wide range of numerical computing tasks. Additionally, we show how the mathematical basis for a probabilistic solution involving a class of stochastic differential equations can leverage those simulations to provide solutions for a range of broadly applicable computational tasks. Despite being in an early development stage, we find that NMC platforms, at a sufficient scale, can drastically reduce the energy demands of high-performance computing (HPC) platforms.
Open access
preprint2020arXiv
Constant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication
Boolean circuits of McCulloch-Pitts threshold gates are a classic model of neural computation studied heavily in the late 20th century as a model of general computation. Recent advances in large-scale neural computing hardware has made their practical implementation a near-term possibility. We describe a theoretical approach for multiplying two N by N matrices that integrates threshold gate logic with conventional fast matrix multiplication algorithms, that perform O(Nω) arithmetic operations for a positive constant ω<3. Our approach converts such a fast matrix multiplication algorithm into a constant-depth threshold circuit with approximately O(Nω) gates. Prior to our work, it was not known whether the Θ(N3)-gate barrier for matrix multiplication was surmountable by constant-depth threshold circuits. Dense matrix multiplication is a core operation in convolutional neural network training. Performing this work on a neural architecture instead of off-loading it to a GPU may be an appealing option.
Open access
preprint2020arXiv
Probing a Set of Trajectories to Maximize Captured Information
We study a trajectory analysis problem we call the Trajectory Capture Problem (TCP), in which, for a given input set T of trajectories in the plane, and an integer k≥2, we seek to compute a set of k points (``portals'') to maximize the total weight of all subtrajectories of T between pairs of portals. This problem naturally arises in trajectory analysis and summarization. We show that the TCP is NP-hard (even in very special cases) and give some first approximation results. Our main focus is on attacking the TCP with practical algorithm-engineering approaches, including integer linear programming (to solve instances to provable optimality) and local search methods. We study the integrality gap arising from such approaches. We analyze our methods on different classes of data, including benchmark instances that we generate. Our goal is to understand the best performing heuristics, based on both solution time and solution quality. We demonstrate that we are able to compute provably optimal solutions for real-world instances.
Open access
preprint2016arXiv
Benchmarking Adiabatic Quantum Optimization for Complex Network Analysis
We lay the foundation for a benchmarking methodology for assessing current and future quantum computers. We pose and begin addressing fundamental questions about how to fairly compare computational devices at vastly different stages of technological maturity. We critically evaluate and offer our own contributions to current quantum benchmarking efforts, in particular those involving adiabatic quantum computation and the Adiabatic Quantum Optimizers produced by D-Wave Systems, Inc. We find that the performance of D-Wave's Adiabatic Quantum Optimizers scales roughly on par with classical approaches for some hard combinatorial optimization problems; however, architectural limitations of D-Wave devices present a significant hurdle in evaluating real-world applications. In addition to identifying and isolating such limitations, we develop algorithmic tools for circumventing these limitations on future D-Wave devices, assuming they continue to grow and mature at an exponential rate for the next several years.
Open access
preprint2016arXiv
Generalized Hypergraph Matching via Iterated Packing and Local Ratio
In k-hypergraph matching, we are given a collection of sets of size at most k, each with an associated weight, and we seek a maximum-weight subcollection whose sets are pairwise disjoint. More generally, in k-hypergraph b-matching, instead of disjointness we require that every element appears in at most b sets of the subcollection. Our main result is a linear-programming based (k−1+k1)-approximation algorithm for k-hypergraph b-matching. This settles the integrality gap when k is one more than a prime power, since it matches a previously-known lower bound. When the hypergraph is bipartite, we are able to improve the approximation ratio to k−1, which is also best possible relative to the natural LP. These results are obtained using a more careful application of the \emph{iterated packing} method. Using the bipartite algorithmic integrality gap upper bound, we show that for the family of combinatorial auctions in which anyone can win at most t items, there is a truthful-in-expectation polynomial-time auction that t-approximately maximizes social welfare. We also show that our results directly imply new approximations for a generalization of the recently introduced bounded-color matching problem. We also consider the generalization of b-matching to \emph{demand matching}, where edges have nonuniform demand values. The best known approximation algorithm for this problem has ratio 2k on k-hypergraphs. We give a new algorithm, based on local ratio, that obtains the same approximation ratio in a much simpler way.
Open access
preprint2016arXiv
Geometric Hitting Set for Segments of Few Orientations
We study several natural instances of the geometric hitting set problem for input consisting of sets of line segments (and rays, lines) having a small number of distinct slopes. These problems model path monitoring (e.g., on road networks) using the fewest sensors (the "hitting points"). We give approximation algorithms for cases including (i) lines of 3 slopes in the plane, (ii) vertical lines and horizontal segments, (iii) pairs of horizontal/vertical segments. We give hardness and hardness of approximation results for these problems. We prove that the hitting set problem for vertical lines and horizontal rays is polynomially solvable.
Open access
preprint2016arXiv
Iterative Packing for Demand and Hypergraph Matching
Iterative rounding has enjoyed tremendous success in elegantly resolving open questions regarding the approximability of problems dominated by covering constraints. Although iterative rounding methods have been applied to packing problems, no single method has emerged that matches the effectiveness and simplicity afforded by the covering case. We offer a simple iterative packing technique that retains features of Jain's seminal approach, including the property that the magnitude of the fractional value of the element rounded during each iteration has a direct impact on the approximation guarantee. We apply iterative packing to generalized matching problems including demand matching and k-column-sparse column-restricted packing (k-CS-PIP) and obtain approximation algorithms that essentially settle the integrality gap for these problems. We present a simple deterministic 2k-approximation for k-CS-PIP, where an 8k-approximation was the best deterministic algorithm previously known. The integrality gap in this case is at least 2(k−1+1/k). We also give a deterministic 3-approximation for a generalization of demand matching, settling its natural integrality gap.
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.