Efficiently Controllable Graphs

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 (6)

• The Magnus expansion and some of its applications
• Quantum Computation as Geometry
• Optimal control, geometry, and quantum computing
• An information theoretical analysis of quantum optimal control
• Local controllability of quantum networks
• Universal quantum interfaces

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