Decomposing classical matrices into linear combinations of Pauli strings is a major bottleneck for end-to-end implementations of near-term quantum algorithms. In this work, we consider a promise version of this Pauli decomposition problem in which the matrix is guaranteed to have support on only k=poly(n) Pauli strings and is given through classical sparse query access. Existing Pauli decomposition algorithms are designed for the generic, dense problem and do not inherently take advantage of this promised sparsity, so these approaches take time that is exponential in n. We present a randomized classical algorithm that does take advantage of this sparsity and recovers the exact Pauli decomposition with success probability at least 1−δ, for any δ. Under the stated access model, the algorithm executes with query and runtime complexity that is polynomial in n, k, and log(1/δ). These results show that, even though finding the Pauli decomposition is exponentially hard for general matrices, it becomes efficiently solvable for matrices that are known to be sparse in the Pauli basis, a regime that is relevant to near-term quantum algorithms operating on structured classical input.
To process a problem with a Quantum Processing Unit (QPU), it must be transformed into a sequence of quantum operators, or gates. These operators are either packed into a query (i.e. quantum algorithm primitive) that encodes the problem, or used to construct the cost function for Variationnal Quantum Algorithm (VQA). Typical queries are the problem Hamiltonian Simulation (HS) and the problem Block-Encoding (BEing). To construct the circuits associated with the quantum description, the problem must be mapped as a Linear Combination of Hamiltonian (LCH) or a Linear Combination of nitaries (LCU) matrices. All the summed Hamiltonian matrices or unitary matrices must have a known decomposition in basic gates. The complexity of this query should be incorporated into the quantum algorithm's query complexity, thereby limiting the processing possibilities of QPU for many problems. In this work, we propose Hamiltonian matrices used to map the problem of interest, and that behave like a single qubit when expressed in the appropriate basis. It leads to a framework, the Special Tripotent Hamiltonian (STH) Framework, able to implement most of the typical problems considered for quantum computing. These methods address many problems implemented on QPUs, ranging from second-quantization chemistry operators to graphs associated with Partial Differential Equations (PDE), sparse matrices, and higher-order optimization problems. This work underlines interesting properties associated with the STH basic gate decomposition. These include the ability to switch between LCH and LCU, map non-Hermitian problems, and construct the quantum circuit queries required for quantum computing. We also provide a list of STH that are used for the matrix decomposition of many structured matrices. These structured matrices are associated with graph adjacency matrices that can be combined to implement structured matrices.
We present three new quantum algorithms in the quantum query model for \textsc{graph-collision} problem: \begin{itemize} \item an algorithm based on tree decomposition that uses $O\left(\sqrt{n}t^{\sfrac{1}{6}}\right)$ queries where t is the treewidth of the graph; \item an algorithm constructed on a span program that improves a result by Gavinsky and Ito. The algorithm uses O(n+α∗∗) queries, where α∗∗(G) is a graph parameter defined by α∗∗(G):=minVC– vertex cover ofGmaxI⊆VCI– independent set∑v∈I°v; \item an algorithm for a subclass of circulant graphs that uses O(n) queries. \end{itemize} We also present an example of a possibly difficult graph G for which all the known graphs fail to solve graph collision in O(nlogcn) queries.
Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning n-qubit quantum unitaries U and Hamiltonians H, given query access to U or the unitary evolution of H, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form U=∑iαiCi over Cliffords Ci with bounded Clifford extent ∑i∣αi∣. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary U with optimal Clifford fidelity opt, outputs a Clifford unitary witnessing fidelity ≥opt−ε for some error ε>0, in time poly(n,(1/ε)log(1/ε)). We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity Ω(2n)) in the Pauli basis but are Clifford structured.