Efficiently Controllable Graphs
arXiv:1503.05270 · doi:10.1103/PhysRevLett.118.260501
Abstract
We investigate graphs that can be disconnected into small components by removing a vanishingly small fraction of their vertices. We show that when a quantum network is described by such a graph, the network is efficiently controllable, in the sense that universal quantum computation can be performed using a control sequence polynomial in the size of the network while controlling a vanishingly small fraction of subsystems. We show that networks corresponding to finite-dimensional lattices are efficently controllable, and explore generalizations to percolation clusters and random graphs. We show that the classical computational complexity of estimating the ground state of Hamiltonians described by controllable graphs is polynomial in the number of subsystems/qubits.
References in corpus (19)
- Community detection in graphs
- Resilience of the Internet to random breakdowns
- Dynamical Decoupling of Open Quantum Systems
- Breakdown of the Internet under intentional attack
- The Magnus expansion and some of its applications
- Quantum Computation as Geometry
- Controllability of quantum mechanical systems by root space decomposition of su(N)
- Optimal control, geometry, and quantum computing
- Quantum chaos: an introduction via chains of interacting spins-1/2
- An information theoretical analysis of quantum optimal control
- Scalable quantum computation via local control of only two qubits
- Local controllability of quantum networks
- Crossover from Poisson to Wigner-Dyson Level Statistics in Spin Chains with Integrability Breaking
- Symmetry Principles in Quantum Systems Theory
- Zero forcing, linear and quantum controllability for systems evolving on networks
- Universal quantum interfaces
- Control by quantum dynamics on graphs
- Computation on Spin Chains with Limited Access
- Approximation algorithms for QMA-complete problems
Cited by in corpus (7)
- From pulses to circuits and back again: A quantum optimal control perspective on variational quantum algorithms
- Reconfigurable optical implementation of quantum complex networks
- Dependence of the Quantum Speed Limit on System Size and Control Complexity
- Controlling qubit networks in polynomial time
- Lie algebra for rotational subsystems of a driven asymmetric top
- Graph test of controllability in qubit arrays: A systematic way to determine the minimum number of external controls
- Algebra and Hilbert space structures induced by quantum probes