Article
Computer Science, Artificial Intelligence
Giovanni Acampora, Ferdinando Di Martino, Alfredo Massa, Roberto Schiattarella, Autilia Vitiello
Summary: This paper introduces the concept of Distributed Noisy-Intermediate Scale Quantum (D-NISQ) as a reference computational model to design innovative frameworks for quantum devices to interact and solve complex problems collaboratively. Through two case studies, a multi-threaded implementation of the D-NISQ model demonstrates greater reliability in solving problems through quantum computation.
INFORMATION FUSION
(2023)
Article
Quantum Science & Technology
Vivien Vandaele, Simon Martiel, Timothee Goubault de Brugiere
Summary: We propose a framework for synthesizing phase polynomials that can handle both fully and partially connected NISQ architectures. Our algorithms generally produce circuits with lower CNOT counts and depths compared to the state of the art, or achieve similar performances with significantly shorter running times. Additionally, we introduce methods that can be used with our algorithms to trade an increase in CNOT count for a decrease in execution time, bridging the gap between our algorithms and faster ones.
QUANTUM SCIENCE AND TECHNOLOGY
(2022)
Review
Computer Science, Interdisciplinary Applications
Jaiteg Singh, Kamalpreet Singh Bhangu
Summary: This study aims to develop a clear understanding of the promises and limitations of the current state-of-the-art quantum computing use cases and to define directions for future research. It bridges the gap between computer professionals and non-physicists by offering conceptual and notational information and surveys existing applications, technological advancements, and contemporary challenges associated with quantum computing.
ARCHIVES OF COMPUTATIONAL METHODS IN ENGINEERING
(2023)
Article
Computer Science, Information Systems
Koustubh Phalak, Swaroop Ghosh
Summary: Quantum Machine Learning (QML) is a rapidly growing field that combines Quantum Computing (QC) and Machine Learning (ML). This paper proposes a shot optimization method for QML models, which can reduce the number of shots without significantly impacting the model performance. The method is tested on MNIST and FMNIST datasets for classification tasks, and also applied to ground state energy estimation of molecules.
Article
Multidisciplinary Sciences
Joshua J. Goings, Alec White, Joonho Lee, Christofer S. Tautermann, Matthias Degroote, Craig Gidney, Toru Shiozaki, Ryan Babbush, Nicholas C. Rubin
Summary: An accurate assessment of the potential computational advantages of quantum computers in chemical simulation is crucial for their deployment. This study explores the resources required for assessing the electronic structure of cytochrome P450 enzymes using quantum and classical computations, defining a boundary for classical-quantum advantage. The results show that simulation of large-scale CYP models has the potential to be a quantum advantage problem, emphasizing the interplay between classical computations and quantum algorithms in chemical simulation.
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
(2022)
Article
Computer Science, Hardware & Architecture
Pau Escofet, Anabel Ovide, Carmen G. Almudever, Eduard Alarcon, Sergi Abadal
Summary: Modular quantum computing architectures offer a promising alternative to overcome the scaling limitations of current quantum computers. To improve the performance and scalability of quantum computing systems, efficient distribution of qubits across multiple processing cores is critical. The Hungarian Qubit Assignment (HQA) algorithm, which considers the interactions between qubits across the circuit, achieves fine-grained partitioning and enhanced qubit utilization. Through comprehensive experiments, the HQA algorithm demonstrates superiority over existing methods, with an average improvement of 1.28x.
IEEE COMPUTER ARCHITECTURE LETTERS
(2023)
Article
Computer Science, Theory & Methods
Enda Yu, Dezun Dong, Xiangke Liao
Summary: This paper proposes a standard for systematically classifying communication optimization algorithms in distributed deep learning systems based on mathematical modeling, which is a novel contribution in the field. The authors categorize existing works into four categories based on communication optimization strategies and discuss potential future challenges and research directions.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2023)
Article
Chemistry, Analytical
Muhammad Asad Ullah, Jason William Setiawan, Junaid Ur Rehman, Hyundong Shin
Summary: This paper evaluates the usefulness and practicality of quantum consensus algorithms for blockchain-enhanced sensor and computing networks, finding that quantum noise generally increases error rates and different consensus schemes are affected to varying degrees. Current quantum protocols with noisy devices and communication can only be used for modular units in enterprise-level blockchains.
Article
Physics, Multidisciplinary
Anderson Avila, Helida Santos, Anderson Cruz, Samuel Xavier-de-Souza, Giancarlo Lucca, Bruno Moura, Adenauer Yamin, Renata Reiser
Summary: This paper introduces the concept and integration process of the HybriD-GM model. The D-GM environment is extended to provide efficient parallel execution for hybrid architectures with CPU and GPU integration. By managing projection operators and exploring memory access patterns, the HybriD-GM model achieves granularity control and optimizes hardware resources in distributed computations organized as tree data structures. In the evaluation, simulations of Shor's and Grover's algorithms show significant performance improvements compared to the previous D-GM version and other related works like LIQUi|⟩ and ProjectQ simulators.
Article
Computer Science, Information Systems
Huan Gao, Xuantong Peng, Qingfeng Guan, Jingyi Wang, Ziqi Liu, Xue Yang, Wen Zeng
Summary: This article presents a parallel raster processing library (mcRPL) that combines multi-process parallelism and multi-thread parallelism to enable parallel raster processing on distributed heterogeneous architectures with multiple CPUs and GPUs. By adopting an adaptive hardware assignment strategy and a series of task-processing strategies, the library can fully utilize the available processors and achieve significantly faster speeds compared to the original serial algorithms. The library also provides user-friendly interfaces to enhance computational performance and enable large-scale raster computing tasks with extensive data volumes.
INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE
(2023)
Article
Computer Science, Artificial Intelligence
Giovanni Acampora, Angela Chiatto, Autilia Vitiello
Summary: This paper discusses the application of quantum computing in optimization problems and proposes the use of genetic algorithms as gradient-free methods to optimize the parameters of Quantum Approximate Optimization Algorithm (QAOA) circuit. Experimental results on noisy quantum devices solving MaxCut problem show that the genetic algorithm outperforms other gradient-free optimizers in terms of approximation ratio.
APPLIED SOFT COMPUTING
(2023)
Article
Computer Science, Information Systems
Giovanni Acampora, Autilia Vitiello
Summary: This study introduces a new evolutionary algorithm utilizing an actual quantum processor, which employs quantum phenomena to achieve significant speed-up in computation. By implementing quantum concepts such as quantum chromosome and entangled crossover, the proposed algorithm efficiently executes genetic evolution on quantum devices to converge towards proper sub-optimal solutions of a given optimization problem. The experimental results show that the synergy between quantum and evolutionary computation leads to a promising bio-inspired optimization strategy.
INFORMATION SCIENCES
(2021)
Article
Computer Science, Artificial Intelligence
Mohammed Zidan, Salem F. Hegazy, Mahmoud Abdel-Aty, Salah S. A. Obayya
Summary: We propose a quantum computation algorithm that can solve the problem of logical equivalence verification exponentially faster than classical deterministic computation. By executing oracles of two evaluated functions, a common target qubit is obtained and interacts with an ancillary qubit, with the degree of entanglement serving as a reliable witness for logical equivalence. The quantum algorithm's steps number is inversely proportional to the square of the measured concurrence value's standard error epsilon 2, independent of the input size.
APPLIED SOFT COMPUTING
(2023)
Review
Chemistry, Multidisciplinary
Mario Motta, Julia E. Rice
Summary: Digital quantum computers provide a computational framework for solving the Schrodinger equation for many-particle systems, with recent remarkable growth in quantum computing algorithms for quantum simulation. This review introduces emerging algorithms for the simulation of Hamiltonian dynamics and eigenstates, focusing on their applications to electronic structure in molecular systems. Theoretical foundations, implementation details, strengths, limitations, and recent advances of the method are discussed.
WILEY INTERDISCIPLINARY REVIEWS-COMPUTATIONAL MOLECULAR SCIENCE
(2022)
Article
Quantum Science & Technology
Pablo Diez-Valle, Jorge Luis-Hita, Senaida Hernandez-Santana, Fernando Martinez-Garcia, Alvaro Diaz-Fernandez, Eva Andres, Juan Jose Garcia-Ripoll, Escolastico Sanchez-Martinez, Diego Porras
Summary: In this paper, we propose a new method for solving combinatorial optimization problems with challenging constraints using Variational Quantum Algorithms (VQAs). We introduce the Multi-Objective Variational Constrained Optimizer (MOVCO) which updates the variational parameters by a classical multi-objective optimization performed by a genetic algorithm. We test this method on a real-world problem in finance and show significant improvement in terms of cost and the avoidance of local minima that do not satisfy mandatory constraints.
QUANTUM SCIENCE AND TECHNOLOGY
(2023)
Article
Computer Science, Information Systems
Fernando G. S. L. Brandao, Aram W. Harrow, James R. Lee, Yuval Peres
IEEE TRANSACTIONS ON INFORMATION THEORY
(2020)
Article
Quantum Science & Technology
Alexander M. Dalzell, Aram W. Harrow, Dax Enshan Koh, Rolando L. La Placa
Editorial Material
Biochemical Research Methods
Prashant S. Emani, Jonathan Warrell, Alan Anticevic, Stefan Bekiranov, Michael Gandal, Michael J. McConnell, Guillermo Sapiro, Alan Aspuru-Guzik, Justin T. Baker, Matteo Bastiani, John D. Murray, Stamatios N. Sotiropoulos, Jacob Taylor, Geetha Senthil, Thomas Lehner, Mark B. Gerstein, Aram W. Harrow
Summary: Quantum computing, leveraging the unique properties of quantum mechanics, addresses the challenges of scale and complexity in biological sciences and facilitates the integration of insights across different areas.
Article
Quantum Science & Technology
Elizabeth Crosson, Aram W. Harrow
Summary: The study analyzes the mixing time of PIMC for 1D stoquastic Hamiltonians, including disordered TIM models with long-range algebraically decaying interactions and disordered XY spin chains with nearest-neighbor interactions. By bounding the convergence time to the equilibrium distribution, the study rigorously justifies the use of PIMC for approximating partition functions and expectations of observables for models with inverse temperatures scaling at most logarithmically with the number of qubits.
Article
Physics, Multidisciplinary
Aram W. Harrow, John C. Napp
Summary: In a natural black-box setting, a quantum variational algorithm that measures analytic gradients of the objective function with a low-depth circuit and performs stochastic gradient descent can converge to an optimum faster than any algorithm that only measures the objective function itself, settling the question of whether measuring analytic gradients in such algorithms can ever be beneficial. Upper bounds on the cost of gradient-based variational optimization near a local minimum are also derived.
PHYSICAL REVIEW LETTERS
(2021)
Article
Physics, Multidisciplinary
John C. Napp, Rolando L. La Placa, Alexander M. Dalzell, Fernando G. S. L. Brandao, Aram W. Harrow
Summary: The advantage of quantum computation over classical computation lies in its ability to efficiently simulate situations that are difficult to simulate on classical computers. We have proven that certain families of random circuits can be approximately simulated on classical computers in linear time, even though they have the capability of universal quantum computation and are hard to simulate exactly. We propose two classical simulation algorithms and provide numerical and analytical evidence for their efficiency.
Article
Physics, Multidisciplinary
Anurag Anshu, Aram W. Harrow, Mehdi Soleimanifar
Summary: This study identifies the structural property of ground-state entanglement in gapped local Hamiltonians and captures it using the entanglement spread, a quantum information quantity. The main result shows that gapped ground states have limited entanglement spread across any partition of the system, exhibiting an area-law scaling.
Article
Physics, Mathematical
Aram W. W. Harrow, Saeed Mehraban
Summary: In this study, we prove that poly(t) . n(1/D)-depth local random quantum circuits with two qudit nearest-neighbor gates on a D-dimensional lattice with n qudits are approximate t-designs in various measures. We also improve the scrambling and decoupling bounds for spatially local random circuits and show that sampling within total variation distance from these circuits is hard for classical computers. Additionally, we demonstrate that O(root n) depth is sufficient for achieving anti-concentration in quantum circuits.
COMMUNICATIONS IN MATHEMATICAL PHYSICS
(2023)
Article
Materials Science, Multidisciplinary
Tianci Zhou, Aram W. Harrow
Summary: A global quantum quench can be simulated using a quantum circuit with local unitary gates. The growth rate of entanglement is determined by the entanglement velocity, which is bounded by the finite light cone resulting from locality. The study shows that the unitary interactions achieving the maximal rate must remain unitary when the space and time directions are exchanged, known as dual unitarity. The results also indicate that maximal entanglement velocity is always accompanied by a specific pattern of entanglement, making the analysis of solvable models simpler.
Article
Quantum Science & Technology
Aram W. Harrow, Linghang Kong, Zi-Wen Liu, Saeed Mehraban, Peter W. Shor
Summary: The study reveals an asymptotic separation between the time scales of the saturation of OTOC and that of entanglement entropy in a random quantum-circuit model, contradicting the intuition that a random quantum circuit mixes in time proportional to the diameter of the underlying graph of interactions. This result provides a more rigorous justification for the argument that black holes may be slow information scramblers, related to the black-hole information problem. The obtained bounds for OTOC are interesting as they generalize previous studies to geometries on graphs in a rigorous and general fashion.
Article
Optics
Adam Bene Watts, Nicole Yunger Halpern, Aram Harrow
Summary: The correspondence principle suggests that quantum systems become classical when large, but agents with limited control can still violate Bell inequalities. Despite earlier literature suggesting otherwise, it is possible for restricted experimentalists to violate a Bell inequality even with increasing experimental errors. The violation implies nonclassicality and can be tested with photons, solid-state systems, atoms, and trapped ions, although it does not disprove local hidden-variables theories. By rejecting the goal of disproof, nonclassical correlations can be certified under reasonable experimental assumptions.
Proceedings Paper
Computer Science, Theory & Methods
Aram W. Harrow, Saeed Mehraban, Mehdi Soleimanifar
PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20)
(2020)
Proceedings Paper
Computer Science, Theory & Methods
Aram W. Harro, Annie Y. Wei
PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20)
(2020)
Article
Optics
Joseph X. Lin, Joseph A. Formaggio, Aram W. Harrow, Anand Natarajan
Article
Astronomy & Astrophysics
Annie Y. Wei, Preksha Naik, Aram W. Harrow, Jesse Thaler