More Like this

1. Graph Sketching against Adaptive Adversaries Applied to the Minimum Degree Algorithm

   https://doi.org/􏰇􏰈􏰫􏰇􏰇􏰈􏰑􏰩􏰠􏰮􏰣􏰙􏰫􏰌􏰈􏰇􏰍􏰫􏰈􏰈􏰈􏰇􏰑􏰇􏰈􏰫􏰇􏰇􏰈􏰑􏰩􏰠􏰮􏰣􏰙􏰫􏰌􏰈􏰇􏰍􏰫􏰈􏰈􏰈􏰇􏰑􏰇􏰈􏰫􏰇􏰇􏰈􏰑􏰩􏰠􏰮􏰣􏰙􏰫􏰌􏰈􏰇􏰍􏰫􏰈􏰈􏰈􏰇􏰑􏰇􏰈􏰫􏰇􏰇􏰈􏰑􏰩􏰠􏰮􏰣􏰙􏰫􏰌􏰈􏰇􏰍􏰫􏰈􏰈􏰈􏰇􏰑10.1109/FOCS.2018.00019  

   Fahrbach, Matthew ; Miller, Gary L. ; Peng, Richard ; Sawlani, Saurabh ; Wang, Junxing ; Xu, Shen Chen ( October 2018 , 2018 IEEE 59th Annual Symposium on Foundations of Computer Science)

   Abstract—Motivated by the study of matrix elimination orderings in combinatorial scientific computing, we utilize graph sketching and local sampling to give a data structure that provides access to approximate fill degrees of a matrix undergoing elimination in polylogarithmic time per elimination and query. We then study the problem of using this data structure in the minimum degree algorithm, which is a widely- used heuristic for producing elimination orderings for sparse matrices by repeatedly eliminating the vertex with (approx- imate) minimum fill degree. This leads to a nearly-linear time algorithm for generating approximate greedy minimum degree orderings. Despite extensive studies of algorithms for elimination orderings in combinatorial scientific computing, our result is the first rigorous incorporation of randomized tools in this setting, as well as the first nearly-linear time algorithm for producing elimination orderings with provable approximation guarantees. While our sketching data structure readily works in the oblivious adversary model, by repeatedly querying and greed- ily updating itself, it enters the adaptive adversarial model where the underlying sketches become prone to failure due to dependency issues with their internal randomness. We show how to use an additional sampling procedure to circumvent this problem and to create an independent access sequence. Our technique for decorrelating interleaved queries and updates to this randomized data structure may be of independent interest. 

   more » « less
2. Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation

   https://doi.org/10.1109/HPEC55821.2022.9926353  

   Ibrahim, Cameron ; Lykov, Danylo ; He, Zichang ; Alexeev, Yuri ; Safro, Ilya ( September 2022 , 2022 IEEE High Performance Extreme Computing Conference (HPEC))

   One of the key problems in tensor network based quantum circuit simulation is the construction of a contraction tree which minimizes the cost of the simulation, where the cost can be expressed in the number of operations as a proxy for the simulation running time. This same problem arises in a variety of application areas, such as combinatorial scientific computing, marginalization in probabilistic graphical models, and solving constraint satisfaction problems. In this paper, we reduce the computationally hard portion of this problem to one of graph linear ordering, and demonstrate how existing approaches in this area can be utilized to achieve results up to several orders of magnitude better than existing state of the art methods for the same running time. To do so, we introduce a novel polynomial time algorithm for constructing an optimal contraction tree from a given order. Furthermore, we introduce a fast and high quality linear ordering solver, and demonstrate its applicability as a heuristic for providing orderings for contraction trees. Finally, we compare our solver with competing methods for constructing contraction trees in quantum circuit simulation on a collection of randomly generated Quantum Approximate Optimization Algorithm Max Cut circuits and show that our method achieves superior results on a majority of tested quantum circuits. Reproducibility: Our source code and data are available at https://github.com/cameton/HPEC2022_ContractionTrees. 

   more » « less
3. Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation

   Cameron Ibrahim, Danylo Lykov ( January 2022 , IEEE High Performance Extreme Computing (HPEC))

   One of the key problems in tensor network based quantum circuit simulation is the construction of a contraction tree which minimizes the cost of the simulation, where the cost can be expressed in the number of operations as a proxy for the simulation running time. This same problem arises in a variety of application areas, such as combinatorial scientific computing, marginalization in probabilistic graphical models, and solving constraint satisfaction problems. In this paper, we reduce the computationally hard portion of this problem to one of graph linear ordering, and demonstrate how existing approaches in this area can be utilized to achieve results up to several orders of magnitude better than existing state of the art methods for the same running time. To do so, we introduce a novel polynomial time algorithm for constructing an optimal contraction tree from a given order. Furthermore, we introduce a fast and high quality linear ordering solver, and demonstrate its applicability as a heuristic for providing orderings for contraction trees. Finally, we compare our solver with competing methods for constructing contraction trees in quantum circuit simulation on a collection of randomly generated Quantum Approximate Optimization Algorithm Max Cut circuits and show that our method achieves superior results on a majority of tested quantum circuits. Reproducibility: Our source code and data are available at https://github.com/cameton/HPEC2022 ContractionTrees. 

   more » « less
4. Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation

   Cameron Ibrahim ; Danylo Lykov ; Zichang He ; Yuri Alexeev ; Ilya Safro ( September 2022 , IEEE High Performance Extreme Computing Conference (HPEC))

   One of the key problems in tensor network based quantum circuit simulation is the construction of a contraction tree which minimizes the cost of the simulation, where the cost can be expressed in the number of operations as a proxy for the simulation running time. This same problem arises in a variety of application areas, such as combinatorial scientific computing, marginalization in probabilistic graphical models, and solving constraint satisfaction problems. In this paper, we reduce the computationally hard portion of this problem to one of graph linear ordering, and demonstrate how existing approaches in this area can be utilized to achieve results up to several orders of magnitude better than existing state of the art methods for the same running time. To do so, we introduce a novel polynomial time algorithm for constructing an optimal contraction tree from a given order. Furthermore, we introduce a fast and high quality linear ordering solver, and demonstrate its applicability as a heuristic for providing orderings for contraction trees. Finally, we compare our solver with competing methods for constructing contraction trees in quantum circuit simulation on a collection of randomly generated Quantum Approximate Optimization Algorithm Max Cut circuits and show that our method achieves superior results on a majority of tested quantum circuits. Reproducibility: Our source code and data are available at https://github.com/cameton/HPEC2022_ContractionTrees. 

   more » « less
5. Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Up-date

   Derezinski, Michal ; Lacotte, Jonathan ; Pilanci, Mert ; Mahoney, Michael W. ( January 2021 , Advances in neural information processing systems)

   In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. Randomized sketching has emerged as a powerful technique for constructing estimates of the Hessian which can be used to perform approximate Newton steps. This involves multiplication by a random sketching matrix, which introduces a trade-off between the computational cost of sketching and the convergence rate of the optimization algorithm. A theoretically desirable but practically much too expensive choice is to use a dense Gaussian sketching matrix, which produces unbiased estimates of the exact Newton step and which offers strong problem-independent convergence guarantees. We show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching, without substantially affecting its convergence properties. This approach, called Newton LESS, is based on a recently introduced sketching technique: LEverage Score Sparsified (LESS) embeddings. We prove that Newton-LESS enjoys nearly the same problem-independent local convergence rate as Gaussian embeddings, not just up to constant factors but even down to lower order terms, for a large class of optimization tasks. In particular, this leads to a new state-of-the-art convergence result for an iterative least squares solver. Finally, we extend LESS embeddings to include uniformly sparsified random sign matrices which can be implemented efficiently and which perform well in numerical experiments. 

   more » « less