In a recent preprint by Deutsch et al. [1995] the authors suggest the possibility of polynomial approximability of arbitrary unitary operations on $n$ qubits by 2-qubit unitary operations. We address that comment by proving strong lower bounds on the approximation capabilities of g-qubit unitary operations for fixed g. We consider approximation of unitary operations on subspaces as well as approximation of states and of density matrices by quantum circuits in several natural metrics. The ability of quantum circuits to probabilistically solve decision problem and guess checkable functions is discussed. We also address exact unitary representation by reducing the upper bound by a factor of n^2 and by formalizing the argument given by Barenco et al. [1995] for the lower bound. The overall conclusion is that almost all problems are hard to solve with quantum circuits.
In a recent preprint by Deutsch et al. [1995] the authors suggest the possibility of polynomial approximability of arbitrary unitary operations on n qubits by 2-qubit unitary operations. We address that comment by proving strong lower bounds on the approximation capabilities of g-qubit unitary operations for fixed g. We consider approximation of unitary operations on subspaces as well as approximation of states and of density matrices by quantum circuits in several natural metrics. The ability of quantum circuits to probabilistically solve decision problem and guess checkable functions is discussed. We also address exact unitary representation by reducing the upper bound by a factor of n^2 and by formalizing the argument given by Barenco et al. [1995] for the lower bound. The overall conclusion is that almost all problems are hard to solve with quantum circuits.
Quantum computers promise to solve important problems faster than conventional computers ever could. Underneath is a fundamentally different computational primitive that introduces new challenges for the development of software tools that aid designers of corresponding quantum algorithms. The different computational primitives render classical simulation of quantum circuits particularly challenging. While the logic simulation of conventional circuits is comparatively simple with linear complexity with respect to the number of gates, quantum circuit simulation has to deal with the exponential memory requirements to represent quantum states on non-quantum hardware with respect to the number of qubits. Decision Diagrams (DDs) address this challenge through exploitation of redundancies in matrices and vectors to provide significantly more compact representations in many cases. Moreover, the probabilistic nature of quantum computations enables another angle to tackle the complexity: Quantum algorithms are resistant to some degree against small inaccuracies in the quantum state as these only lead to small changes in the outcome probabilities. We propose to exploit this resistance against (small) errors to gain even more compact decision diagrams. In this work, we investigate the potential of approximation in quantum circuit simulation in detail. To this end, we first present four dedicated schemes that exploit the error resistance and efficiently approximate quantum states represented by decision diagrams. Subsequently, we propose two simulation strategies that utilize those approximations schemes in order to improve the efficiency of DD-based quantum circuit simulation, while, at the same time, allowing the user to control the resulting degradation in accuracy. We empirically show that the proposed approximation schemes reduce the size of decision diagrams substantially and also analytically prove the effect of multiple approximations on the attained accuracy. Eventually, this enables speed-ups of the resulting approximate quantum circuit simulation of up to several orders of magnitudes—again, while controlling the fidelity of the result.
We define the model of quantum circuits with density matrices, where non-unitary gates are allowed. Measurements in the middle of the computation, noise and decoherence are implemented in a natural way in this model, which is shown to be equivalent in computational power to standard quantum circuits. The main result in this paper is a solution for the subroutine problem: The general function that a quantum circuit outputs is a probabilistic function, but using pure state language, such a function can not be used as a black box in other computations. We give a natural definition of using general subroutines, and analyze their computational power. We suggest convenient metrics for quantum computing with mixed states. For density matrices we analyze the so called ``trace metric'', and using this metric, we define and discuss the ``diamond metric'' on superoperators. These metrics enable a formal discussion of errors in the computation. Using a ``causality'' lemma for density matrices, we also prove a simple lower bound for probabilistic functions.
The ability (or inability) to represent or approximate Boolean functions by polynomials is a central concept in complexity theory, underlying interactive and probabilistically checkable proof systems, circuit lower bounds, quantum complexity theory, and more. In this book, the authors survey what is known about a particularly natural notion of approximation by polynomials, capturing pointwise approximation over This book covers recent progress on proving approximate degree lower and upper bounds and describes some applications of the new bounds to oracle separations, quantum query and communication complexity, and circuit complexity. The authors explain how several of these advances have been unlocked by a particularly simple and elegant technique, called dual block composition, for constructing solutions to this dual linear program. They also provide concise coverage of even more recent lower bound techniques based on a new complexity measure called spectral sensitivity. Finally, they show how explicit constructions of approximating polynomials have been inspired by quantum query algorithms. This book provides a comprehensive review of the foundational and recent developments of an important topic in both classical and quantum computing. The reader has a considerable body of knowledge condensed in an accessible form to quickly understand the principles and further their own research.
Efficient measures to determine the similarity of quantum states, such as the fidelity metric, have been widely studied. In this paper, we address the problem of defining a similarity measure for quantum operations that can be efficiently estimated. Given two quantum operations, U1 and U2, represented in their circuit forms, we first develop a quantum sampling circuit to estimate the normalized Schatten 2-norm of their difference ($\ensuremath{\parallel}{U}_{1}\ensuremath{-}{U}_{2}{\ensuremath{\parallel}}_{{S}_{2}}$) with precision $\ensuremath{\epsilon}$, using only one clean qubit and one classical random variable. We prove a $\text{Poly}(\frac{1}{\ensuremath{\epsilon}})$ upper bound on the sample complexity, which is independent of the size of the quantum system. We then show that such a similarity metric is directly related to a functional definition of similarity of unitary operations using the conventional fidelity metric of quantum states (F): If $\ensuremath{\parallel}{U}_{1}\ensuremath{-}{U}_{2}{\ensuremath{\parallel}}_{{S}_{2}}$ is sufficiently small (e.g., $\ensuremath{\le}\frac{\ensuremath{\epsilon}}{1+\sqrt{2(1/\ensuremath{\delta}\ensuremath{-}1)}}$) then the fidelity of states obtained by processing the same randomly and uniformly picked pure state $|\ensuremath{\psi}\ensuremath{\rangle}$ is as high as needed $[\mathcal{F}({U}_{1}|\ensuremath{\psi}\ensuremath{\rangle},{U}_{2}|\ensuremath{\psi}\ensuremath{\rangle})\ensuremath{\ge}1\ensuremath{-}\ensuremath{\epsilon}]$ with probability exceeding $1\ensuremath{-}\ensuremath{\delta}$. We provide example applications of this efficient similarity metric estimation framework to quantum circuit learning tasks, such as finding the square root of a given unitary operation.
The local Hamiltonian (LH) problem is the canonical QMA-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on n qubits cannot be solved classically in time O(2(1−ε)n) for any ε>0 under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time O(2(1−ε)n/2) for any ε>0 under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved.
Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of QMA problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in O(2n) time for an arbitrary 1/poly(n) relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime.
To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a T-time quantum circuit acting on N qubits into a (d+1)-local Hamiltonian acting on N+O(T1/d) qubits. This improves the standard construction based on the unary clock, which uses N+O(T) qubits.
We introduce the problem of unitarization. Unitarization is the problem of taking k input quantum circuits that produce orthogonal states from the all 0 state, and create an output circuit implementing a unitary with its first k columns as those states. That is, the output circuit takes the kth computational basis state to the state prepared by the kth input circuit. We allow the output circuit to use ancilla qubits initialized to 0. But ancilla qubits must always be returned to 0 for any input. The input circuits may use ancilla qubits, but we are only guaranteed the they return ancilla qubits to 0 on the all 0 input. The unitarization problem seems hard if the output states are neither orthogonal to or in the span of the computational basis states that need to map to them. In this work, we approximately solve this problem in the case where input circuits are given as black box oracles by probably finding an approximate basis for our states. This method may be more interesting than the application. This technique is a sort of quantum analogue of Gram-Schmidt orthogonalization for quantum states. Specifically, we find an approximate basis in polynomial time for the following parameters. Take any natural n, k=O(ln(ln(n))ln(n)), and ε=2−O(ln(n)). Take any k input quantum states, (∣ψi⟩)i∈[k], on polynomial in n qubits prepared by quantum oracles, (Vi)i∈[k] (that we can control call and control invert). Then there is a quantum circuit with polynomial size in n with access to the oracles (Vi)i∈[k] that with at least 1−ε probability, computes at most k circuits with size polynomial in n and oracle access to (Vi)i∈[k] that ε approximately computes an ε approximate orthonormal basis for (∣ψi⟩)i∈[k].