Characterization of Quantum States Based on Creation Complexity. Issue 9 (28th August 2020)

• Record Type: Journal Article
• Authors: Hu, Zixuan; Kais, Sabre
• Is Part Of: Advanced quantum technologies. Volume 3:Issue 9(2020)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2020-08-28
• Subjects: quantum algorithms -- quantum computation -- quantum state complexity; Quantum theory -- Periodicals; Quantum computing -- Periodicals; Quantum chemistry -- Periodicals; Quantum electronics -- Periodicals; 537.5
• DOI: 10.1002/qute.202000043
• Languages: English
• ISSNs: 2511-9044

Abstract

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, it is first shown that 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. Then, it is shown that 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, an efficient coefficient sampling procedure can be designed to determine if the state 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. Abstract : In this study, quantum states are characterized dependent on creation complexity. It is shown that a large class of quantum states with polynomial creation complexity can be characterized by common coefficient features such that an efficient coefficient sampling procedure can determine if any given state belongs to the class. The partial knowledge of a state's creation complexity can improve quantum algorithm design.