Intermediate measurements let quantum computations discard information and reuse their workspace. Deferring all measurements can require storing their entire history, which need not preserve logarithmic space. Fefferman and Remscrim proved that measurements can nevertheless be eliminated with two-sided bounded error, and asked whether the same holds with one-sided error [FR21]. We prove RQLΓ = RQULΓ for the standard gate set Γ = {H, T, CNOT}, preserving polynomial time, logarithmic space, and exactly zero acceptance on no-instances. Our proof extends the density-matrix doubling method of Girish, Raz and Zhan [ GRZ21 ] to general channels, including resets and classical memory. We also prove measurement elimination for broader finite gate sets with exact inverses, including suitable gates with transcendental entries, and establish gate-set independence for a specified family of algebraic gate sets. A separate history-checking construction proves QMAL1,G = QUMAL1,G under explicit gate assumptions: measurements can also be eliminated from logarithmic-space quantum verification while preserving perfect completeness
Space-bounded computation has been a central topic in classical and quantum complexity theory. In the quantum case, every elementary gate must be unitary. This restriction makes it unclear whether the power of space-bounded computation changes by allowing intermediate measurement. In the bounded error case, Fefferman and Remscrim [STOC 2021, pp.1343--1356] and Girish, Raz and Zhan~[ICALP 2021, pp.73:1--73:20] recently provided the break-through results that the power does not change. This paper shows that a similar result holds for space-bounded quantum computation with postselection. Namely, it is proved possible to eliminate intermediate postselections and measurements in the space-bounded quantum computation in the bounded-error setting. Our result strengthens the recent result by Le Gall, Nishimura and Yakaryilmaz~[TQC 2021, pp.10:1--10:17] that logarithmic-space bounded-error quantum computation with intermediate postselections and measurements is equivalent in computational power to logarithmic-space unbounded-error probabilistic computation. As an application, it is shown that bounded-error space-bounded one-clean qubit computation (DQC1) with postselection is equivalent in computational power to unbounded-error space-bounded probabilistic computation, and the computational supremacy of the bounded-error space-bounded DQC1 is interpreted in complexity-theoretic terms.
We show that quantum algorithms of time
T and space
S≥logT with unitary operations and intermediate measurements can be simulated by quantum algorithms of time
T⋅poly(S) and space $ {O}(S\cdot \log T)$ with unitary operations and without intermediate measurements. The best results prior to this work required either
Ω(T) space (by the deferred measurement principle) or
poly(2S) time [FR21,GRZ21]. Our result is thus a time-efficient and space-efficient simulation of algorithms with unitary operations and intermediate measurements by algorithms with unitary operations and without intermediate measurements. To prove our result, we study pseudorandom generators for quantum space-bounded algorithms. We show that (an instance of) the INW pseudorandom generator for classical space-bounded algorithms [INW94] also fools quantum space-bounded algorithms. More precisely, we show that for quantum space-bounded algorithms that have access to a read-once tape consisting of random bits, the final state of the algorithm when the random bits are drawn from the uniform distribution is nearly identical to the final state when the random bits are drawn using the INW pseudorandom generator. This result applies to general quantum algorithms which can apply unitary operations, perform intermediate measurements and reset qubits.
General quantum computation consists of unitary operations and also measurements. It is well known that intermediate quantum measurements can be deferred to the end of the computation, resulting in an equivalent purely unitary computation. While time efficient, this transformation blows up the space to linear in the running time, which could be super-polynomial for low-space algorithms. Fefferman and Remscrim (STOC'21) and Girish, Raz and Zhan (ICALP'21) show different transformations which are space efficient, but blow up the running time by a factor that is exponential in the space. This leaves the case of algorithms with small-but-super-logarithmic space as incurring a large blowup in either time or space complexity. We show that such a blowup is likely inherent, demonstrating that any "black-box" transformation which removes intermediate measurements must significantly blow up either space or time.
This paper presents a general space-efficient method for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness c and soundness s, either with or without a witness (corresponding to QMA and BQP, respectively). To convert this computation into a new computation with error at most 2^{-p}, the most space-efficient method known requires extra workspace of O(p*log(1/(c-s))) qubits. This space requirement is too large for scenarios like logarithmic-space quantum computations. This paper shows an errorreduction method for unitary quantum computations (i.e., computations without intermediate measurements) that requires extra workspace of just O(log(p/(c-s))) qubits. This in particular gives the first method of strong amplification for logarithmic-space unitary quantum computations with two-sided bounded error. This also leads to a number of consequences in complexity theory, such as the uselessness of quantum witnesses in bounded-error logarithmic-space unitary quantum computations, the PSPACE upper bound for QMA with exponentially-small completeness-soundness gap, and strong amplification for matchgate computations.
We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most 1. The algorithm gets as an input an arbitrary n× n contraction matrix A, and a parameter T ≤ poly(n) and outputs the entries of A^T, up to (arbitrary) polynomially small additive error. The algorithm applies only unitary operators, without intermediate measurements. We show various implications and applications of this result: First, we use this algorithm to show that the class of quantum logspace algorithms with only quantum memory and with intermediate measurements is equivalent to the class of quantum logspace algorithms with only quantum memory without intermediate measurements. This shows that the deferred-measurement principle, a fundamental principle of quantum computing, applies also for quantum logspace algorithms (without classical memory). More generally, we give a quantum algorithm with space O(S + log T) that takes as an input the description of a quantum algorithm with quantum space S and time T, with intermediate measurements (without classical memory), and simulates it unitarily with polynomially small error, without intermediate measurements. Since unitary transformations are reversible (while measurements are irreversible) an interesting aspect of this result is that it shows that any quantum logspace algorithm (without classical memory) can be simulated by a reversible quantum logspace algorithm. This proves a quantum analogue of the result of Lange, McKenzie and Tapp that deterministic logspace is equal to reversible logspace [Lange et al., 2000]. Finally, we use our results to show non-trivial classical simulations of quantum logspace learning algorithms.
Driven by exploring the power of quantum computation with a limited number of qubits, we present a novel complete characterization for space-bounded quantum computation, which encompasses settings with one-sided error (unitary
coRQL) and two-sided error (
BQL), approached from a quantum state testing perspective: - The first family of natural complete problems for unitary
coRQL, namely space-bounded quantum state certification for trace distance and Hilbert-Schmidt distance; - A new family of natural complete problems for
BQL, namely space-bounded quantum state testing for trace distance, Hilbert-Schmidt distance, and (von Neumann) entropy difference. In the space-bounded quantum state testing problem, we consider two logarithmic-qubit quantum circuits (devices) denoted as
Q0 and
Q1, which prepare quantum states
ρ0 and
ρ1, respectively, with access to their ``source code''. Our goal is to decide whether
ρ0 is
ε1-close to or
ε2-far from
ρ1 with respect to a specified distance-like measure. Interestingly, unlike time-bounded state testing problems, which exhibit computational hardness depending on the chosen distance-like measure, our results reveal that the space-bounded state testing problems, considering all three measures, are computationally as easy as preparing quantum states. Our results primarily build upon a space-efficient variant of the quantum singular value transformation (QSVT) introduced by Gilyén, Su, Low, and Wiebe (STOC 2019), which is of independent interest. Our technique provides a unified approach for designing space-bounded quantum algorithms. Specifically, we show that implementing QSVT for any bounded polynomial that approximates a piecewise-smooth function incurs only a constant overhead in terms of the space required for special forms of the projected unitary encoding.