Pseudo-dimension of quantum circuits
Matthias C. Caro, Ishaun Datta
Abstract
Abstract We characterize the expressive power of quantum circuits with the pseudo-dimension, a measure of complexity for probabilistic concept classes. We prove pseudo-dimension bounds on the output probability distributions of quantum circuits; the upper bounds are polynomial in circuit depth and number of gates. Using these bounds, we exhibit a class of circuit output states out of which at least one has exponential gate complexity of state preparation, and moreover demonstrate that quantum circuits of known polynomial size and depth are PAC-learnable.
Topics & Concepts
MathematicsQuantum circuitPolynomialDiscrete mathematicsCircuit complexityElectronic circuitQuantumQuantum algorithmClass (philosophy)Measure (data warehouse)Quantum computerQuantum error correctionProbabilistic logicQuantum gateState (computer science)Topology (electrical circuits)Exponential functionComplexity classBoolean functionQuantum networkTime complexityUpper and lower boundsStatistical physicsQuantum informationQuantum operationQuantum mechanicsBoolean circuitQuantum stateQuantum complexity theoryPower (physics)Quantum capacityPhysicsComputer scienceQuantum Computing Algorithms and ArchitectureComplexity and Algorithms in GraphsMachine Learning and Algorithms