Characterization of quantum states based on creation complexity
arXiv:2004.13827 · doi:10.1002/qute.202000043
Abstract
The creation complexity of a quantum state is the minimum number of elementary gates required to create it from a basic initial state. The creation complexity of quantum states is closely related to the complexity of quantum circuits, which is crucial in developing efficient quantum algorithms that can outperform classical algorithms. A major question unanswered so far is what quantum states can be created with a number of elementary gates that scales polynomially with the number of qubits. In this work we first show for an entirely general quantum state it is exponentially hard (requires a number of steps that scales exponentially with the number of qubits) to determine if the creation complexity is polynomial. We then show it is possible for a large class of quantum states with polynomial creation complexity to have common coefficient features such that given any candidate quantum state we can design an efficient coefficient sampling procedure to determine if it belongs to the class or not with arbitrarily high success probability. Consequently partial knowledge of a quantum state's creation complexity is obtained, which can be useful for designing quantum circuits and algorithms involving such a state.
arXiv commentRevised version 2
References in corpus (17)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Machine Learning
- A variational eigenvalue solver on a quantum processor
- Quantum algorithm for solving linear systems of equations
- Quantum Simulation
- Adiabatic Quantum Computing
- Quantum Chemistry in the Age of Quantum Computing
- Universal Linear Optics
- Quantum algorithms: an overview
- Quantum annealing with more than one hundred qubits
- Experimental Comparison of Two Quantum Computing Architectures
- Review of Decoherence Free Subspaces, Noiseless Subsystems, and Dynamical Decoupling
- A quantum algorithm for evolving open quantum dynamics on quantum computing devices
- Quantum Machine Learning for Electronic Structure Calculations
- Quantum algorithm for simulating the dynamics of an open quantum system