Characterizing large-scale quantum devices is challenging because quantum noise processes are complex. We present a method for efficiently characterizing general operations in quantum devices with signal-to-noise ratios independent of the system size.

Quantum Information and Measurement (QIM)Jan 1, 20190 citations

Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm

Natsuto Isogai, Hayata Yamasaki, Sho Sonoda +1 more

quant-pharXiv:2605.13979May 15, 20260 citations

Quantum Information and Computation

Efficient quantum algorithms for analyzing large sparse electrical networks

Wang-Guo-Ming

Published Sep 1, 2017• 0 citations

Publisher

Abstract

DOI: 10.5555/3179568.3179573

Related papers

Efficient quantum algorithms for analyzing large sparse electrical networks

Guoming Wang

Analyzing large sparse electrical networks is a fundamental task in physics, electrical engineering and computer science. We propose two classes of quantum algorithms for this task. The first class is based on solving linear systems, and the second class is based on using quantum walks. These algorithms compute various electrical quantities, including voltages, currents, dissipated powers and effective resistances, in time poly(d, c,log(N), 1/λ, 1/e), where N is the number of vertices in the network, d is the maximum unweighted degree of the vertices, c is the ratio of largest to smallest edge resistance, λ is the spectral gap of the normalized Laplacian of the network, and e is the accuracy. Furthermore, we show that the polynomial dependence on 1/λ is necessary. This implies that our algorithms are optimal up to polynomial factors and cannot be significantly improved.Analyzing large sparse electrical networks is a fundamental task in physics, electrical engineering and computer science. We propose two classes of quantum algorithms for this task. The first class is based on solving linear systems, and the second class is based on using quantum walks. These algorithms compute various electrical quantities, including voltages, currents, dissipated powers and effective resistances, in time poly(d, c,log(N), 1/λ, 1/e), where N is the number of vertices in the network, d is the maximum unweighted degree of the vertices, c is the ratio of largest to smallest edge resistance, λ is the spectral gap of the normalized Laplacian of the network, and e is the accuracy. Furthermore, we show that the polynomial dependence on 1/λ is necessary. This implies that our algorithms are optimal up to polynomial factors and cannot be significantly improved.

arXiv:1311.1851Quantum Information and ComputationSep 1, 201727 citations

Towards Large-Scale Quantum Networks

Wojciech Kozlowski, Stephanie Wehner

The vision of a quantum internet is to fundamentally enhance Internet technology by enabling quantum communication between any two points on Earth. While the first realisations of small scale quantum networks are expected in the near future, scaling such networks presents immense challenges to physics, computer science and engineering. Here, we provide a gentle introduction to quantum networking targeted at computer scientists, and survey the state of the art. We proceed to discuss key challenges for computer science in order to make such networks a reality.The vision of a quantum internet is to fundamentally enhance Internet technology by enabling quantum communication between any two points on Earth. While the first realisations of small scale quantum networks are expected in the near future, scaling such networks presents immense challenges to physics, computer science and engineering. Here, we provide a gentle introduction to quantum networking targeted at computer scientists, and survey the state of the art. We proceed to discuss key challenges for computer science in order to make such networks a reality.

arXiv:1909.08396ACM International Conference on Nanoscale Computing and Communication (NANOCOM)Sep 25, 2019150 citations

Quantum networks: General theory and applications

Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D’Ariano +1 more

Quantum networks: General theory and applications In this work we present a general mathematical framework to deal with

arXiv:1601.04864Acta Physica Slovaca Reviews and TutorialsJun 1, 201139 citations

On the quantum simulation of complex networks

Duarte Magano, João P. Moutinho, Bruno Coelho Coutinho

Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.

arXiv:2212.06126SciPost Physics CoreAug 24, 20236 citations

Characterizing large-scale quantum devices

Joel J. Wallman, Joseph Emerson

Quantum Information and Measurement (QIM)Jan 1, 20190 citations

Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm

Natsuto Isogai, Hayata Yamasaki, Sho Sonoda +1 more

Quantum machine learning (QML) aims to accelerate machine learning tasks by exploiting quantum computation. Previous work studied a QML algorithm for selecting sparse subnetworks from large shallow neural networks. Instead of directly solving an optimization problem over a large-scale network, this algorithm constructs a sparse subnetwork by sampling hidden nodes from an optimized probability distribution defined using the ridgelet transform. The quantum algorithm performs this sampling in time $O(D)$ in the data dimension $D$ , whereas a naive classical implementation relies on handling exponentially many candidate nodes and hence takes $\exp[O(D)]$ time. In this work, we construct and analyze a quantum-inspired fully classical algorithm for the same sampling task. We show that our algorithm runs in time $O(\operatorname{poly}(D))$ , thereby removing the exponential dependence on $D$ from the previous classical approach. Numerical simulations show that the proposed sampler achieves empirical risk comparable to exact sampling from the optimized distribution and substantially lower than sampling from the non-optimized uniform distribution, while also exhibiting exponentially improved runtime scaling compared with the conventional classical implementation. These successful dequantization results show that sparse subnetwork selection via optimized sampling can be achieved classically with polynomial data-dimension scaling on conventional computers without quantum hardware, providing an alternative to the existing quantum algorithm.Quantum machine learning (QML) aims to accelerate machine learning tasks by exploiting quantum computation. Previous work studied a QML algorithm for selecting sparse subnetworks from large shallow neural networks. Instead of directly solving an optimization problem over a large-scale network, this algorithm constructs a sparse subnetwork by sampling hidden nodes from an optimized probability distribution defined using the ridgelet transform. The quantum algorithm performs this sampling in time $O(D)$ in the data dimension $D$, whereas a naive classical implementation relies on handling exponentially many candidate nodes and hence takes $\exp[O(D)]$ time. In this work, we construct and analyze a quantum-inspired fully classical algorithm for the same sampling task. We show that our algorithm runs in time $O(\operatorname{poly}(D))$, thereby removing the exponential dependence on $D$ from the previous classical approach. Numerical simulations show that the proposed sampler achieves empirical risk comparable to exact sampling from the optimized distribution and substantially lower than sampling from the non-optimized uniform distribution, while also exhibiting exponentially improved runtime scaling compared with the conventional classical implementation. These successful dequantization results show that sparse subnetwork selection via optimized sampling can be achieved classically with polynomial data-dimension scaling on conventional computers without quantum hardware, providing an alternative to the existing quantum algorithm.

quant-pharXiv:2605.13979May 15, 20260 citations

O(D)

in the data dimension

D

, whereas a naive classical implementation relies on handling exponentially many candidate nodes and hence takes

\exp[O(D)]

time. In this work, we construct and analyze a quantum-inspired fully classical algorithm for the same sampling task. We show that our algorithm runs in time

O(\operatorname{poly}(D))

, thereby removing the exponential dependence on

D

from the previous classical approach. Numerical simulations show that the proposed sampler achieves empirical risk comparable to exact sampling from the optimized distribution and substantially lower than sampling from the non-optimized uniform distribution, while also exhibiting exponentially improved runtime scaling compared with the conventional classical implementation. These successful dequantization results show that sparse subnetwork selection via optimized sampling can be achieved classically with polynomial data-dimension scaling on conventional computers without quantum hardware, providing an alternative to the existing quantum algorithm.