# Efficient quantum algorithms for analyzing large sparse electrical networks

@article{Wang2017EfficientQA, title={Efficient quantum algorithms for analyzing large sparse electrical networks}, author={Guoming Wang}, journal={Quantum Inf. Comput.}, year={2017}, volume={17}, pages={987-1026} }

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 $\operatorname{poly}(d, c, \operatorname{log}(N), 1/\lambda, 1/\epsilon… Expand

#### 18 Citations

Linear and nonlinear quantum algorithms made explicit

- Computer Science
- 2019

A thorough breakdown of common quantum algorithms into their component parts, and the explicit cost of each component in terms of fundamental quantum gates is given, and a new state-of-the-art algorithm for producing a superposition of all permutations is determined. Expand

Quantum Algorithms for Systems of Linear Equations Inspired by Adiabatic Quantum Computing.

- Physics, Medicine
- Physical review letters
- 2019

Two quantum algorithms based on evolution randomization, a simple variant of adiabatic quantum computing, to prepare a quantum state |x⟩ that is proportional to the solution of the system of linear equations Ax[over →]=b[ over →], yielding an exponential quantum speed-up under some assumptions. Expand

Improved quantum backtracking algorithms through effective resistance estimates

- Mathematics, Physics
- ArXiv
- 2017

This work presents a generalisation of one of Montanaro's algorithms to trees containing $k \geq 1$ marked vertices, and achieves the conjectured bound of $\widetilde{\mathcal{O}}(\sqrt{TR_{\mathrm{max}}})$ for finding a single marked vertex and k(k)(k T R R) for finding all $k$ marked Vertices. Expand

The Grover search as a naturally occurring phenomenon

- Computer Science, Physics
- Physical review letters
- 2020

First evidence that under certain conditions, 1/2-spin fermions may naturally behave like a Grover search, looking for topological defects in a material is provided, hinting at novel applications of QW search. Expand

An overview of quantum cellular automata

- Physics, Computer Science
- Natural Computing
- 2019

An overview of quantum cellular automata theory is given, with particular focus on structure results; computability and universality results; and quantum simulation results. Expand

Dynamical Triangulation Induced by Quantum Walk

- Physics, Computer Science
- Symmetry
- 2020

Numerical simulations show that the number of triangles and the local curvature grow as $\alpha$ and $\beta$ parametrize the way geometry changes upon the local density of the walker, and that, in the long run, flatness emerges. Expand

Quantum walk speedup of backtracking algorithms

- Computer Science, Physics
- Theory Comput.
- 2018

A general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs), and this quantum algorithm can be used to speed up the DPLL algorithm. Expand

Approximate Span Programs

- Mathematics, Physics
- ICALP
- 2016

It is shown how any span program that decides a problem $f$ can also be used to decide "property testing" versions of $f, or more generally, approximate the span program witness size, a property of the input related to $f$. Expand

Quantum search as a naturally occurring phenomenon

- 2019

Place. Laboratoire d’Informatique et Systèmes (LIS), Natural Computing team (CaNa). Scientific environment : The CaNa research group (Pablo Arrighi, Giuseppe Di Molfetta, Kevin Perrot, Sylvain Sené)… Expand

The Dirac equation as a quantum walk over the honeycomb and triangular lattices

- Physics, Computer Science
- ArXiv
- 2018

It is shown that the Dirac equation in $(2+1)$ dimensions can be simulated, through local unitaries, on the honeycomb or the triangular lattice, both of interest in the study of quantum propagation on the nonrectangular grids, as in graphene-like materials. Expand

#### References

SHOWING 1-10 OF 99 REFERENCES

Solving Laplacian Systems in Logarithmic Space

- Mathematics, Computer Science
- ArXiv
- 2016

This paper shows that for systems of linear equations in the Laplacian matrix of graphs, the same logarithmic space complexity can actually be achieved by a classical (i.e., non-quantum) algorithm. Expand

Quantum Walks and Electric Networks

- Physics, Mathematics
- 2013

We prove that a quantum walk can detect the presence of a marked element in a graph in $O(\sqrt{WR})$ steps for any initial probability distribution on vertices. Here, $W$ is the total weight of the… Expand

Quantum lower bounds by polynomials

- Mathematics, Computer Science
- Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280)
- 1998

This work examines the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}/sup N/ in the black-box model and gives asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Expand

The electrical resistance of a graph captures its commute and cover times

- Mathematics, Computer Science
- computational complexity
- 2005

Known relations between random walks and electrical networks are extended by showing that resistance in this network is intimately connected with the lengths of random walks on the graph, and bounds on cover time obtained are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix. Expand

Exponential improvement in precision for simulating sparse Hamiltonians

- Computer Science, Physics
- STOC
- 2014

The algorithm is based on a significantly improved simulation of the continuous- and fractional- query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. Expand

Random walks and electric networks

- Computer Science, Mathematics
- 1984

The goal will be to interpret Polya’s beautiful theorem that a random walker on an infinite street network in d-dimensional space is bound to return to the starting point when d = 2, but has a positive probability of escaping to infinity without returning to the Starting Point when d ≥ 3, and to prove the theorem using techniques from classical electrical theory. Expand

Efficient Quantum Algorithms for Simulating Sparse Hamiltonians

- Mathematics, Physics
- 2007

We present an efficient quantum algorithm for simulating the evolution of a quantum state for a sparse Hamiltonian H over a given time t in terms of a procedure for computing the matrix entries of H.… Expand

Quantum speed-up of Markov chain based algorithms

- Mathematics, Computer Science
- 45th Annual IEEE Symposium on Foundations of Computer Science
- 2004

It is shown that under certain conditions, the quantum version of the Markov chain gives rise to a quadratic speed-up, and that the quantum escape time, just like its classical version, depends on the spectral properties of the transition matrix with the marked rows and columns deleted. Expand

Oscillatory localization of quantum walks analyzed by classical electric circuits

- Physics
- 2016

Discrete-time quantum walks are well-known for exhibiting localization, a quantum phenomenon where the walker remains at its initial location with high probability. In companion with a joint Letter,… Expand

Quantum Algorithms for Quantum Field Theories

- Physics, Medicine
- Science
- 2012

A quantum algorithm to compute relativistic scattering probabilities in a massive quantum field theory with quartic self-interactions in spacetime of four and fewer dimensions is developed and achieves exponential speedup over the fastest known classical algorithm. Expand