{'fraction_non_alphanumeric': 0.0743744112708359, 'fraction_numerical': 0.013208010812139083, 'mean_word_length': 4.033498247783962, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Eliminating Intermediate Measurements in Space-Bounded Quantum Computation

A foundational result in the theory of quantum computation known as the"principle of safe storage"shows that it is always possible to take a quantum circuit and produce an equivalent circuit that makes all measurements at the end of the computation. While this procedure is time efficient, meaning that it does not introduce a large overhead in the number of gates, it uses extra ancillary qubits and so is not generally space efficient. It is quite natural to ask whether it is possible to defer measurements to the end of a quantum computation without increasing the number of ancillary qubits. We give an affirmative answer to this question by exhibiting a procedure to eliminate all intermediate measurements that is simultaneously space-efficient and time-efficient. A key component of our approach, which may be of independent interest, involves showing that the well-conditioned versions of many standard linear-algebraic problems may be solved by a quantum computer in less space than seems possible by a classical computer.


Introduction
Quantum computation has the potential to obtain dramatic speedups for important problems such as quantum simulation (see, e.g., [19,28]) and integer factorization [43]. While fully scalable, faulttolerant quantum computers may still be far from fruition, we have now entered at an exciting era in which impressive but resource constrained quantum experiments are being implemented in many academic and industrial labs. As the field transitions from "proof of principle" demonstrations of provable quantum advantage to solving useful problems on near-term experiments, it is particularly critical to characterize the algorithmic power of feasible models of quantum computations that have restrictive resources such as "time" (i.e., the number of gates in the circuit) and "space" (i.e., the number of qubits on which the circuit operates) and to understand how these resources can be traded-off.
A foundational question in this area asks if it is possible to space-efficiently defer intermediate measurements in a quantum computation (see e.g., [18,23,31,35,45,[49][50][51]). While a classic result known as the "principle of safe storage" states that it is always possible to time-efficiently defer intermediate measurements to the end of a computation (see e.g., [2,33]), this procedure uses extra ancilla qubits and so is not generally space-efficient. More specifically, if a quantum circuit Q acts on s qubits and performs m intermediate measurements, the circuit Q ′ constructed using this principle operates on s + poly(m) qubits; if, for example, s = O(log t) and m = Θ(t), this entails an exponential blowup in the amount of needed space.
Our main result solves this problem. We show that every problem solvable with a quantum computation that acts on a designated number of qubits can also be solved by a "unitary" quantum algorithm that uses the same space and makes all measurements at the end of the computation. Stated more formally in the language of complexity theory, we let BQ U SPACE(s(n)) (resp. BQSPACE(s(n))) denote the class of promise problems recognizable with two-sided bounded-error by a uniform family of unitary (resp. general) quantum circuits, where, for each input of length n, there is a corresponding circuit that operates on O(s(n)) qubits and has 2 O(s(n)) gates. Note that it is standard to require that the running time of a computation is at most exponential in its space-bound; see, for instance, [31,49,51] for the importance of this restriction in quantum spacebounded computation, as well as [39] for the importance of the analogous restriction in probabilistic space-bounded computation. Furthermore, let QMASPACE(s(n)) denote those promise problems recognized by a quantum Merlin-Arthur protocol that operates in space O(s(n)) and time 2 O(s(n)) .
Our main result is: Remark. To the best of our knowledge, the containment BPSPACE(s(n)) ⊆ BQ U SPACE(s(n)) was not known to hold, where BPSPACE(s(n)) denotes the analogously defined class of language recognizable by a probabilistic algorithm in space O(s(n)) (and time 2 O(s(n)) ); see, for instance, [31,50] for previous discussion of this question. As one would expect quantum computation to generalize probabilistic computation, the lack of a proof of this containment was unfortunate. Since it is clear that BPSPACE(s(n)) ⊆ BQSPACE(s(n)), we have as a corollary of Theorem 1, that BPSPACE(s(n)) ⊆ BQ U SPACE(s(n)), resolving this question.
Before proceeding further, it is worthwhile to briefly discuss why it is desirable to be able to eliminate intermediate measurements. Firstly, quantum measurements are a natural resource, much as time and space are; in addition to the general desirability of using as few resources as possible in any sort of computational task, it is especially desirable to avoid intermediate measurements, due to the technical challenges involved in implementing such measurements and resetting such qubits to their initial states (for a discussion of these issues from an experimental perspective see, e.g., [14]). Secondly, unitary computations are reversible. The ability to "undo" a unitary subroutine, by running that subroutine in reverse, is used routinely in the design and analysis of quantum algorithms (see, for instance, [6,17,18,30,32,44,53]). Moreover, reversible computations may be performed without generating heat [27]. Thirdly, by demonstrating that unitary quantum space and general quantum space are (polynomially) equivalent in power, we show that the definition of quantum space is quite robust, as allowing intermediate measurements, or even general quantum operations, does not affect the definition of BQ U SPACE(s(n)).
We also study the one-sided (bounded-error and unbounded-error) analogues of the aforementioned two-sided bounded-error space-bounded quantum complexity classes. We show the following results (see Section 2.2 for definitions of the complexity classes appearing in the following theorems).
Proposition 5. poly-conditioned-DET is BQ U L-complete (and, therefore, BQL-complete) To briefly explain the significance of the question posed by Boix-Adserà, Eldar, and Mehraban [8], note that their result shows poly-conditioned-DET ∈ DSPACE(log 2 (n)poly(log log n)). Therefore, as poly-conditioned-DET is BQL-complete, the statement BQL ⊆ DSPACE(log 2−ǫ n) would follow from either a small improvement in their result (i.e., proving a stronger upper bound on the needed amount of deterministic space in terms of κ(n)) or from a small improvement in our result (i.e., proving κ(n)-conditioned-DET remains BQL-hard for subpolynomial κ(n)). Recall that the strongest currently known "dequantumization" result of this type is the classic result of Watrous [51], which states BQL ⊆ DSPACE(log 2 n) (cf. the strongest currently known "derandomization" result of this type, given by Saks and Zhou [40], which states BPL ⊆ DSPACE(log 3 2 n)). In particular, if BQL ⊆ DSPACE(log 2−ǫ n), ∀ǫ > 0, then both our result and the result of Boix-Adserà, Eldar, and Mehraban are essentially optimal.
In Section 4, we study well-conditioned versions of the "standard" C = L-complete problems. We will observe that the relationship of these problems to the one-sided error versions of spacebounded quantum complexity classes is very much analogous to the relationship, discussed earlier, of the well-conditioned versions of the "standard" DET * -complete problems to the two-sided error versions of space-bounded quantum complexity classes. This enables us to prove Theorem 2 and Theorem 3, which concern the relative power of unitary and general quantum space in the one-sided error cases.
In Section 5, we establish the BQ U L-completeness of "scaled-down" versions of certain QMAcomplete problems and certain DQC1-complete problems. We conclude by stating several open problems related to our work in Section 6.

General Notation and Definitions
Let Mat(n) = C n×n denote the set of all n × n complex matrices and let Herm(n) = {A ∈ Mat(n) : A = A † } denote the set of all n×n Hermitian matrices. For A ∈ Mat(n), let σ 1 (A) ≥ · · · ≥ σ n (A) ≥ 0 denote its singular values and let λ 1 (A), . . . , λ n (A) ∈ C denote its eigenvalues; if A ∈ Herm(n), then λ j (A) ∈ R, ∀j, and we order the eigenvalues such that λ 1 (A) ≥ · · · ≥ λ n (A). Let I n denote the n × n identity matrix, Pos(n) = {A ∈ Herm(n) : λ n (A) ≥ 0} denote the n × n positive semidefinite matrices, Proj(n) = {A ∈ Pos(n) : A 2 = A} denote the n × n projection matrices, U(n) = {A ∈ Mat(n) : AA † = I n } denote the n × n unitary matrices, and Den(n) = {A ∈ Pos(V ) : tr(A) = 1} denote the n × n density matrices. Let Q[i] n = { r+ci d : r, c, d ∈ Z, |r|, |c|, |d| ≤ 2 O(n) } denote the set of all O(n)-bit Gaussian rationals and let Mat(n) (resp. Herm(n), Pos(n), etc.) denote the subset of Mat(n) (resp. Herm(n), Pos(n), etc.) which consist of those matrices whose entries are all O(n)-bit Gaussian rationals. For a sequence of matrices A 1 , . . . , A m , and for indices j 1 , j 2 , where We consider parameterized promise problems of the form P = (P n,f 1 ,...,f h ) n∈N , for functions f 1 , . . . , f h : N → R; P n,f 1 ,...,f h consists of instances of size n which satisfy various conditions expressed in terms of f 1 (n), . . . , f h (n). For a promise problem P defined over some alphabet Σ, we, by slight abuse of notation, also write P to denote the subset of Σ * that satisfies the promise; analogously, we write P n,f 1 ,...,f h to denote those instances of size n that satisfy the promise. For X ∈ P, let P( X ) ∈ {0, 1} denote the desired output on input X. We also use the notation P = (P 1 , P 0 ), where P j = { X ∈ P : P( X ) = j}.
We say that P = (P n,f 1 ,...,f h ) n∈N is many-one reducible to where each p j is a real (h + 1)-variate polynomial, such that ∀n ∈ N, ∃g n : . . , f h (n)), ∀j, and (3) such that P( X ) = P ′ (g n ( X )), ∀ X ∈ P n,f 1 ,...,f h . If (g n ) n∈N is computable in deterministic logspace (resp. uniform NC 1 , uniform AC 0 ), we write P ≤ m L P ′ (resp. P ≤ m NC 1 P ′ , P ≤ m AC 0 P ′ ). For a complexity class C, we say that P ′ is C-complete if (1) P ′ ∈ C and (2) P ≤ m L P ′ , ∀P ∈ C. We assume that the reader has familiarity with quantum computation and the theory of quantum information; see, for instance, [24,33,54] for an introduction. A quantum system, on s qubits, that is in a pure state is described by a unit vector |ψ in the 2 s -dimensional Hilbert space C 2 s . A mixed state of the same system is described by some ensemble {(p i , |ψ i ) : i ∈ I}, for some index set I, where p i ∈ [0, 1] denotes the probability of the system being in the pure state |ψ i ∈ C 2 s , and i p i = 1. This ensemble corresponds to the density matrix A = i p i |ψ i ψ i | ∈ Den(2 s ). Of course, many distinct ensembles correspond to the density matrix A; however, all ensembles that correspond to a particular density matrix will behave the same, for our purposes (see, for instance, [33, Section 2.4] for a detailed discussion of this phenomenon).
Let T(n, m) denote the set of all superoperators of the form Φ : Mat(n) → Mat(m) (i.e., Φ is a C-linear map from the C-vector space Mat(n) to the C-vector space Mat(m)). Let T(n) = T(n, n) and let 1 n ∈ T(n) denote the identity operator. Consider some Φ ∈ T(n, m). We say that Φ is positive if, ∀A ∈ Pos(n), we have Φ(A) ∈ Pos(m). We say that Φ is completely-positive if Φ ⊗ 1 r is positive, ∀r ∈ N, where ⊗ denotes the tensor product. We say that Φ is trace-preserving if tr(Φ(A)) = tr(A), ∀A ∈ Mat(n). If Φ is both completely-positive and trace-preserving, then we say Φ is a quantum channel; let Chan(n, m) = {Φ ∈ T(n, m) : Φ is a quantum channel} denote the set of all such channels, and let Chan(n) = Chan(n, n).
Let vec denote the usual vectorization map that takes a matrix A ∈ Mat(n) to the vector vec(A) ∈ C n 2 consisting of the entries of A (in some fixed order). For Φ ∈ T(n), let K(Φ) ∈ Mat(n 2 ) denote the natural representation of Φ, which is defined to be the (unique) matrix for which vec(Φ(A)) = K(Φ)vec(A), ∀A ∈ Mat(n).

Space-Bounded Quantum Computation
We now briefly recall the definitions of several needed space-bounded quantum complexity classes. We begin by noting that, in many of the previous papers that considered space-bounded quantum computation [23,31,35,45,[49][50][51][52], the quantum Turing machine model was used to define the various complexity classes of interest. Arguably, this is the "natural" model to be used to define these classes. However, as the (equivalent) model of uniformly generated quantum circuits are, arguably, more familiar to quantum complexity theorists and physicists, we state these definitions using quantum circuits. We emphasize that all of the results in this paper apply to both the uniform quantum circuit model and the quantum Turing machine model. Definition 6. A (unitary) quantum circuit is a sequence of quantum gates, each of which is a member of some fixed set of gates that is universal for quantum computation (e.g., {H,CNOT,T}). We say that a family of quantum circuits {Q w : w ∈ P} is DSPACE(s(n))-uniform if there is a deterministic Turing machine that, on any input w ∈ P, runs in space O(s(|w|)) (and hence time 2 O(s(|w|)) ), and outputs a description of Q w . Definition 7. Consider functions c, k : N → [0, 1] and s : N → N, with s(n) = Ω(log n), all of which are computable in DSPACE(s(n)). Let Q U SPACE(s(n)) c(n),k(n) denote the collection of all promise problems P = (P 1 , P 0 ) such that there is a DSPACE(s(n))-uniform family of (unitary) quantum circuits {Q w : w ∈ P}, where Q w acts on h w = O(s(|w|)) qubits and has 2 O(s(|w|)) gates, which has the following properties. The circuit Q w is applied to h w qubits that were initialized in the all-zeros state |0 hw , after which the first qubit is measured in the standard basis. If the result is 1, then we say Q w accepts w; if, instead, the result is 0, then we say Q w rejects w. Let Π 1 = |1 1| ⊗ I 2 hw −1 . We require that the following conditions hold: Note that, in the preceding definitions, Q w has 2 O(s(|w|)) gates (this requirement is immediately forced by the uniformity condition). That is to say, in our definition of quantum space s(n), we require that the computation also runs in time 2 O(s(|w|)) . We refer the reader to the excellent survey paper by Saks [39] for a thorough discussion of the desirability of requiring that space-bounded probabilistic computations run in time at most exponential in their space bound, as well as to, for instance, [31,49,51] for discussions of the analogous issue for quantum computations.
Definition 8. We then define unitary quantum space s(n) for a variety of types of error, as follows.
Then, for X ∈ {B, R, N}, let XQ U L = XQ U SPACE(log n) denote unitary quantum logspace with error-bounds specified by the modifier X.
Note that the particular choice of universal gateset does not affect the definition of the twosided bounded-error classes BQ U SPACE(s(n)) (in particular, of BQ U L) due to the space-efficient version [31] of the Solovay-Kitaev theorem; however, the definitions of the one-sided (bounded and unbounded) error classes are, potentially, gateset dependent. Furthermore, note that the class BQ U L would remain the same if defined as BQ U L = Q U SPACE(log n) c(n),k(n) for any c, k for which ∃q : N → N >0 , where q(n) = poly(n), such that c(n) − k(n) ≥ 1 q(n) , ∀n [17]; an analogous claim holds for RQ U L [49].
We next consider general space-bounded quantum computation. Most basically, we wish to define a model of quantum computation that allows intermediate quantum measurements. That is to say, rather than considering a purely unitary quantum computation in which a single measurement is performed at the end of the computation, we now allow measurements to be performed throughout the computation, and for the the results of those measurements to be used to control the computation. As we wish for our main result (the fact that unitary and general space-bounded quantum computation are equivalent in power) to be as strong as possible, we wish to define a model of general space-bounded quantum computation that is as powerful as possible. To that end, we will define a space-bounded variant of the general quantum circuit model considered in the classic paper of Aharonov, Kitaev, and Nisan [2], in which gates are now arbitrary quantum channels.

Definition 9.
A general quantum circuit on h qubits is a sequence Φ = (Φ 1 , . . . , Φ t ) of quantum channels, where each Φ j ∈ Chan(2 h ). By slight abuse of notation, we use Φ to denote the element Φ t • · · · • Φ 1 ∈ Chan(2 h ) obtained by composing the individual gates of the circuit in order. We say that a family of general quantum circuits {Φ w = (Φ w,1 , . . . , Φ w,tw ) : w ∈ P} is DSPACE(s(n))uniform if there is a deterministic Turing machine that, on any input w ∈ P, runs in space O(s(|w|)) (and hence time 2 O(s(|w|)) ), and outputs a description of Φ w ; to be precise, a description of Φ w consists of the entries of each K(Φ w,j ), where we require that K(Φ w,j ) ∈ Mat(2 2h ).
Note that the operation of applying a unitary transformation is a special case of a quantum channel, and so the general quantum circuit model extends the ordinary (unitary) quantum circuit model. Moreover, note that the process of performing any (partial or full) quantum measurement in the computational basis is described by a quantum channel and that the form of the preceding definition allows the results of intermediate measurements to be used to control which operations are applied at later stages of the computation (this can be accomplished by using a subset of the qubits as classical bits to store the results of earlier measurements, thereby making these results available to gates that appear later in the computation). It is necessary to establish some reasonable restriction on the complexity of computing a description of each gate of the circuit, as we do not wish to unreasonably increase the power of the model by allowing, for example, non-computable numbers to be used in defining each gate (see, for instance, [31,36,37,51] for further discussion of this issue).
Definition 10. Consider functions c, k : N → [0, 1] and s : N → N, with s(n) = Ω(log n), all of which are computable in DSPACE(s(n)). Let QSPACE(s(n)) c(n),k(n) denote the collection of all promise problems P = (P 1 , P 0 ) such that there is a DSPACE(s(n))-uniform family of general quantum circuits {Φ w : w ∈ P}, where Φ w acts on h w = O(s(|w|)) qubits and has 2 O(s(|w|)) gates, which has the following properties. The circuit Φ w is applied to h w qubits that were initialized in the all-zeros state |0 hw , after which the first qubit is measured in the standard basis. If the result is 1, then Φ w accepts w; otherwise, Φ w rejects w. Let 1 1 ⊗ tr ∈ Chan(2 hw , 2) denote the operation in which all qubits except the first qubit are traced out.
We note that this general quantum circuit model is equivalent to the space-bounded (general) quantum Turing machine model of Watrous [51] (modulo a small issue concerning the precise class of allowed transition amplitudes, in which our definition is slightly more restrictive). We also note that the results of this paper would apply to any "reasonable" variant of space-bounded quantum computation that is classically controlled, which includes all of the "standard" variants that have been considered (see, for instance, [31,35,45,51]). We refer the reader to [31, Section 2] for a thorough discussion of the various models of space-bounded quantum computation, and, in particular, of the reasonableness of requiring classical control; we also discuss the issue of classical vs. quantum control later in Section 6.
Definition 11. We then general quantum space s(n) for each error-type, analogously to the unitary case of Definition 8. BQSPACE(s(n)) = QSPACE(s(n)) 2 3 , 1 3 , BQL = BQSPACE(log n), RQSPACE(s(n)) = QSPACE(s(n)) 1 2 ,0 , etc. Note that the particular choice of constants 2 3 and 1 3 that appear in the definition of BQSPACE are arbitrary, as the completeness and soundness parameters can straightforwardly be amplified; a similar statement holds for RQSPACE. Finally, we define a space-bounded variant of quantum Merlin-Arthur proof systems, essentially following [18].
Definition 12. Consider functions c, k : N → [0, 1] and s : N → N, with s(n) = Ω(log n), all of which are computable in DSPACE(s(n)). Let s(n)−bounded−QMA c(n),k(n) denote the collection of all promise problems P = (P 1 , P 0 ) such that there is a DSPACE(s(n))-uniform family of (unitary) quantum circuits {V w : w ∈ P}, where V w acts on m w + h w = O(s(|w|)) qubits and has 2 O(s(|w|)) gates, which has the following properties. Let Π 1 = |1 1| ⊗ I 2 mw +hw −1 and let Ψ mw denote the set of m w -qubit states. For each w ∈ P, the verification circuit V w is applied to the state |ψ ⊗ |0 hw , where |ψ ∈ Ψ mw is a (purported) proof of the fact that w ∈ P 1 . Then, the first qubit is measured in the standard basis. If the result is 1, then w is accepted; otherwise, w is rejected.
Definition 13. We then define space-bounded QMA, for a variety of types of error, as follows.

Well-Conditioned Determinant
We define the following well-conditioned versions of the standard DET * -complete problems [12].
Note that, with the exception of the problem DET (and DET + ), each of the above problems are defined such that they correspond to approximating some quantity with additive error ǫ/2; In other words, we have defined DET such that it corresponds to obtaining an approximation of ln(|det(A)|) with additive error ǫ/2; this is equivalent to obtaining a e ± ǫ 2 multiplicative approximation of |det(A)|. As we will see in Section 3.1 and Section 3.3, this is the "correct" definition of DET, in the sense that it is the version of the determinant problem that most closely corresponds to the other linear-algebraic problems (matrix powering, matrix inversion, etc.) defined above.
Definition 15. For each promise problem P n,m,κ,ǫ −1 in Definition 14, we define poly-conditioned-P to be the promise problem P n,n O(1) ,n O(1) ,n O(1) . For example,

BQ U L Completeness
We now show that all of the above poly-conditioned problems are BQ U L-complete. By [18, Theorem 13], poly-conditioned-MATINV + is BQ U L-complete (note that the notation used in this paper to express the promised condition number differs from the notation used in [18]). Therefore, it suffices to show that, for each such poly-conditioned-P, we have poly-conditioned-P ≤ m L poly-conditioned-MATINV + and poly-conditioned-MATINV + ≤ m L poly-conditioned-P. Remark. We note that reductions between the standard versions of these problems (i.e., where there is no assumption of being well-conditioned) are well-known [5,12,13,29,[46][47][48]. However, these reductions, generally, do not preserve the property of being poly-conditioned; therefore, we must exhibit reductions that are rather different from the "standard" reductions.
We will prove several lemmas that exhibit reductions between particular problems in Definition 14. The proofs of these lemmas share a common structure: for a pair of promise problems P, P ′ , we show how to transform an instance w ∈ P to an instance f (w) ∈ P ′ such that the reduction function f preserves the answer (i.e., P(w) = P ′ (f (w))) and also preserves the property of being well-conditioned. Note that P ≤ m L P ′ ⇒ poly-conditioned-P ≤ m L poly-conditioned-P ′ . In the following, we assume that m(n), κ(n), and ǫ(n) −1 can be computed to O(log n) bits of precision in uniform AC 0 .
Note that, the proof (which appears in Section 3.2) of Theorem 1 (which states the equivalence between unitary and general quantum space) only requires Lemmas 21 to 23. The remaining lemmas are used to prove the other main results of this paper.
, . . . , n l + nm}}. We then have Moreover, for 1 ≤ j 1 ≤ j 2 ≤ m, we have As shown above, be defined such that R r,c = 1 if r = c or r = 1, and R r,c = 0 otherwise; let A 0 = R ⊗ I n and consist of n×n blocks, where the blocks immediately above the main diagonal blocks are given by A 1 , . . . , A m , and all other entries are 0. Let B = I nm+n − Y ∈ Mat(nm + n) and consider B −1 . We partition B −1 into n × n blocks, where for r, c ∈ {1, . . . , m + 1}, C r,c ∈ Mat(n) denotes the block in block-row r and block-column c. It is straightforward to verify that For k ∈ {1, . . . , nm + n}, let χ k ∈ R nm+n denote the vector that is 1 in entry k and 0 elsewhere; let v = χ s and let u = χ nm+t . Notice that det(B) = 1. By the matrix determinant lemma, Next, observe that By the Sherman-Morrison formula, Let a = ln(1+b−ǫ(n))− l(nm+n) and b = ln(1+b)− l(nm+n). .
This implies We now prove Theorem 4 from Section 1.1, which we restate here for convenience. Proof. By [18,Theorem 13], poly-conditioned-MATINV + is BQ U L-complete. By the preceding lemmas, we have Note that ≤ m AC 0 or ≤ m NC 1 reducibility implies ≤ m L reducibility; further, note that P ≤ m L P ′ ⇒ poly-conditioned-P ≤ m L poly-conditioned-P ′ . Therefore, we conclude that each such poly-conditioned problem is BQ U L-complete.

BQSPACE vs. BQ U SPACE vs. BPSPACE vs. QMASPACE
In this section, we explore the relationships between the classes BQSPACE(s(n)), BQ U SPACE(s(n)), BPSPACE(s(n)), and QMASPACE(s(n)). First, we consider the case in which s(n) = log n. While, trivially, BPL ⊆ BQL, it is not obvious, a priori, that BPL ⊆ BQ U L. To the best of our knowledge, the strongest partial result in this direction is the classic result of Watrous [49,Theorem 4.12], which showed that BPL is contained in a variant of BQ U L in which there is no bound on the running time of the QTM.
By Theorem 4, poly-conditioned-MATPOW ∈ BQ U L. As we next observe, this implies BPL ⊆ BQ U L and, more strongly, BQL = BQ U L. Of course, the statement BQL = BQ U L immediately implies BPL ⊆ BQ U L; nevertheless, we will first show, directly, that BPL ⊆ BQ U L. We then extend these results to any (space-constructible) space bound s(n) = Ω(log n), by use of a standard padding argument.
Proof. Suppose P = (P 1 , P 0 ) ∈ BPL. Then there is some probabilistic TM M that recognizes P with two-sided error ≤ 1 3 within time t(n) = n O(1) and space s(n) = O(log n), for any input w ∈ P of length n = |w|. Let |M | denote the size of the finite control of M , let Γ denote the work-tape alphabet of M , and let c(n) = |M |(n + 2)(s(n))|Γ| s(n) = n O(1) denote the number of possible configurations of M on inputs of length n. It is well-known that, for input w ∈ P, one may construct, in deterministic space O(log(|w|)) a stochastic matrix A w ∈ Mat(c(n)) and values x w , y w ∈ {1, . . . , c(n)} such that A t w [x w , y w ] is precisely the probability that M accepts w within t steps [15,34]. Note that, as A w is stochastic, so is A t w , ∀t ∈ N; this implies 3 and MATPOW( A w , x w , y w , 2 3 ) = P(w). By Theorem 4, MATPOW c(n),t(n), √ c(n),3 ∈ BQ U L, which implies P ∈ BQ U L.
By applying an analogous argument to general quantum Turing machines (where the stochastic matrix that describes a single step of the computation of a probabilistic TM is replaced by the quantum channel that describes a single step of the computation of a quantum TM), we may then show that BQL ⊆ BQ U L (and, therefore, that BQL = BQ U L); for completeness, we include such a proof in Appendix A. Instead, in this section, we exhibit an analogous proof using the general quantum circuits of Definition 9.
Proof. Suppose P = (P 1 , P 0 ) ∈ BQL. By definition, there is some L-uniform family of general quantum circuits {Φ w = (Φ w,1 , . . . , Φ w,tw ) : w ∈ P}, where Φ w acts on h w = O(log|w|) qubits and has t w = |w| O(1) gates, such that if w ∈ P 1 , then Pr[Φ w accepts w] ≥ 2 3 , and if w ∈ P 0 , then Pr[Φ w accepts w] ≤ 1 3 . Without loss of generality we may, for convenience, assume that Φ w "cleansup" its workspace at the end of the computation, by measuring the first qubit in the computational basis, and then forcing every other qubit to the state |0 (by measuring each such qubit in the computational basis and, if the result 1 is obtained, flipping its value).
We now prove Theorem 1, our main result stated in the introduction, which we restate here for convenience. Proof. Clearly, BQ U SPACE(s(n)) ⊆ BQSPACE(s(n)). By [18, Theorem 18 and Theorem 26], QMASPACE(s(n)) = BQ U SPACE(s(n)). All that remains is to show that BQSPACE(s(n)) ⊆ BQ U SPACE(s(n)), which follows from the preceding theorem and a standard padding argument; for the sake of completeness, we now briefly state this argument.
We define P log = (P log 1 , P log 0 ) ⊆ Σ * such that P log j = {w01 2 s(|w|) : w ∈ P j }, for j ∈ {0, 1}. We next show that P log ∈ BQL, by exhibiting a family of general quantum circuits {Φ log x = (Φ log x,1 , . . . , Φ log x,t log x ) : x ∈ P log }, with the appropriate parameters, that recognizes P log . Begin by noticing that, as s is space-constructible, there is a DTM D that uses space O(log n) on all inputs of length n, where, on any input x ∈ Σ * , D checks if x = w01 2 s(|w|) , for some w ∈ Σ * . If x is of this form, then D marks the rightmost symbol of w; otherwise, D rejects. We then construct a DTM M ′ which, on input x ∈ Σ * produces Φ log x , as follows. First, M ′ runs D. If D rejects, then M ′ outputs a trivial single-gate circuit, which acts on a single qubit and always rejects. Otherwise (i.e., when the input x is of the form w01 2 s(|w|) ), M ′ simulates M on the prefix w, producing the circuit Φ w ; note that, in this case, |x| = |w| + 1 + 2 s(|w|) , which implies M ′ runs in space O(s(|w|)) = O(log(2 s(|w|) )) = O(log(|x|)), and that Φ log x acts on h log x = h w = O(s(|w|)) = O(log(|x|)) qubits and has t log x : x ∈ P log } is a L-uniform family of general quantum circuits, with the appropriate parameters, that recognizes P log with two-sided bounded-error 1 3 . Thus, by Theorem 27, P log ∈ BQ U L. To complete the proof, we show that this implies P ∈ BQ U SPACE(s(n)). To see this, let {Q log x : x ∈ P log } denote a L-uniform family of (unitary) quantum circuits that recognizes P log with two-sided bounded-error 1 3 , where Q log x acts on O(log(|x|)) qubits and has |x| O(1) gates, and let M U denote a logspace DTM that produces this circuit family. We then define a DTM M ′ U , which, on input w ∈ Σ * , simply simulates M U on x = w01 2 s(|w|) ; in particular, in order to keep track of the simulated head of M U when it is in the suffix 01 2 s(|w|) , M ′ U marks s(|w|) + 1 cells on its work tape (recall that s is space-constructible), which is then used as a classical counter that can count up to 2 s(|w|)+1 − 1. By an analysis similar to that of the previous paragraph, we see that M ′ U runs in space O(s(n)) and that the circuit family {Q w : w ∈ P} that it produces recognizes P and has the correct parameters.

Fully Logarithmic Approximation Schemes
In this section, we study the class of functions that are well-approximable in quantum logspace, following (essentially) the notation and definitions of [16]. In particular, we work with the general (resp. unitary) quantum Turing machine model, rather than the equivalent model of a uniform family of general (resp. unitary) quantum circuits; of course, all results also apply to the quantum circuit model. For simplicity, throughout this section, we fix the alphabet Σ = {0, 1}. We say that a function f : Σ * → R is poly-bounded if |f (w)| ≤ poly(|w|), ∀w ∈ Σ * . Definition 28. We say that a poly-bounded f has a fully logarithmic quantum approximation scheme FLQAS if there is a (general) quantum TM M f that, on input x, ǫ, δ , where x ∈ Σ * and ǫ, δ ∈ R >0 , runs in time poly(|x|, ǫ −1 , log(δ −1 )) and space O(log(|x|) + log(ǫ −1 ) + log(log(δ −1 ))), and outputs a value y ∈ R such that Pr[|f (x) − y| ≥ ǫ] ≤ δ (to be precise, M f outputs a string that encodes a dyadic rational number y). In other words, with confidence at least 1 − δ, the value y is an additive approximation of f (x) with error at most ǫ. We analogously say that f has a FLQ U AS if M f is a unitary quantum TM, a FLRAS if M f is a randomized TM, and a FLAS if M f is a deterministic TM (where, in this last case, we set δ = 0 and remove the dependence on δ from the time and space bounds).

Following the notation established in Section 2.1 and Definitions 14 and 15, let
In other words, D(poly-matinv) consists of precisely those strings in Σ * that are encodings of instances of a variant of poly-conditioned-MATINV where only the portion of the promise involving singular values is required (i.e., there is no restriction on A −1 [s, t] involving b). We then consider the poly-conditioned matrix inversion function poly-matinv : D(poly-matinv) → C, given by poly-matinv( A, s, t ) = A −1 [s, t]. For consistency with [16], as well as to make the relationship between our results and certain logspace counting classes more clear, we then consider R(poly-matinv(·)) : D(poly-matinv) → R (resp. |poly-matinv(·)| : D(poly-matinv) → R ≥0 ), which are given by the real part (resp. the magnitude) of the poly-conditioned matrix inversion function.
Proof. By [18,Theorem 14] (and the discussion following it), the functions R(poly-matinv(·)) and |poly-matinv(·)| each have a FLQ U AS (to be precise, the aforementioned theorem considered only the case in which A ∈ Pos(n), the general case then follows from the fact that the reduction from MATINV to MATINV + given by Lemma 23 preserves the value of the corresponding entry of the inverse matrix, not merely its magnitude); this improved upon the earlier result of Ta-Shma [45], which showed that these functions each have a FLQAS [16]. Notice that the reduction from ITMATPROD to MATPOW given by Lemma 21, and the reduction from MATPOW to MATINV given by Lemma 22, both also preserve the value of the matrix entry in question, not merely its magnitude. Therefore, R(poly-itmatprod(·)) and |poly-itmatprod(·)| each have a FLQ U AS. Finally, by Lemmas 16, 17 and 20, ln(|poly-det(·)|) has a FLQ U AS.
Note that, following [16], we have defined fully logarithmic (quantum, randomized, etc.) approximation schemes with respect to additive error ǫ; that is to say, we approximate f (x) by a value y such that Pr[|f (x) − y| ≥ ǫ] ≤ δ. We then define a multiplicative fully logarithmic (quantum, randomized, etc.) approximation scheme of a function g : Σ * → R ≥0 as an analogous procedure that produces an approximation z such that Pr[z ∈ [e −ǫ g(x), e ǫ g(x)]] ≤ δ. Note that here, for convenience, we follow the convention (as used in, for example, [21]) that multiplicative approximations are defined using e ±ǫ , rather than the more standard (and essentially equivalent) (1 ± ǫ). Next, recall that by [16,Theorem 6], if BQL = BPL, then every poly-bounded function that has a FLQAS also has a FLRAS (recall that we use BQL and BPL to denote classes of promise problems, which differs from the notation used in [16]). By combining this with the BQ U L-hardness of the various poly-conditioned promise problems (Theorem 4) and our result that BQ U L = BQL (Theorem 27), the following proposition is immediate; we note that a partial version of this proposition was implicit in [15]. (ii) Every poly-bounded function that has a FLQAS also has a FLRAS.
(iii) Every poly-bounded function that has a FLQ U AS also has a FLRAS.
Remark. In particular, the preceding proposition suggests that |poly-det(·)| does not have a multiplicative FLRAS (as this would imply the seemingly unlikely statement BQL = BPL). It is natural to compare this statement with the result of Jerrum, Sinclair, and Vigoda [21] which shows the existence of a (multiplicative) FPRAS (fully polynomial randomized approximation scheme) for the permanent of a nonnegative integer matrix.

Well-Conditioned Singular
We next consider a well-conditioned version of the problem of determining if a matrix is singular. Additionally, following [41], we also consider well-conditioned versions of the "verification" versions of standard DET-complete problems.
Remark. Note that the requirement |b| ≤ κ(n) above is unnecessary due to the fact that, for any matrix M , max s,t |M [s, t]| ≤ σ 1 (M ) (therefore, if |b| > κ(n), which can easily be checked, then the input is a 0 instance). We include this condition only for convenience.
We begin by exhibiting reductions between the above problems; in subsequent sections, we will use these reductions to prove new properties of quantum logspace.

RQSPACE vs. RQ U SPACE vs. RQMASPACE vs. QMASPACE 1
For those promise problems P given in Definition 32, we define poly-conditioned-P as in Definition 15.
Proof. Precisely analogous to the proof of Lemma 26.
Proof. Suppose P = (P 1 , P 0 ) ∈ QMAL 1 . By definition, there is a L-uniform family of (unitary) quantum circuits {V w = (V w,1 , . . . , V w,tw ) : w ∈ P}, where V w acts on m w + h w = O(log|w|) qubits and has t w = poly(|w|) gates, such that w ∈ P 1 ⇒ ∃|ψ ∈ Ψ mw , Pr[V w accepts w, |ψ ] ≥ c = 1, and We make use of the Kitaev clock Hamiltonian construction [24,Section 14.4], in a manner similar to [18,Lemma 21] (though, without the need to first apply space-efficient probability amplification techniques). Let d w = 2 mw+hw (t w + 1) = poly(|w|), define the d w -dimensional Hilbert space H w = C 2 mw ⊗ C 2 hw ⊗ C tw+1 , and let Π b = I 2 b−1 ⊗ |1 1| ⊗ I 2 mw +hw −b ∈ Proj(2 mw+hw ) denote the projection onto the subspace of C 2 mw ⊗ C 2 hw spanned by states in which the b th qubit is 1. We define the Hamiltonians H prop w , H in w , H out w , H w ∈ Pos(d w ) on H w as follows: By [24,Section 14.4], ∃r 0 , r 1 ∈ R >0 , such that , ∀w ∈ P 0 . Therefore, H w ∈ poly-conditioned-SINGULAR and P(w) = SINGULAR( H w ); as {V w : w ∈ P} is L-uniform, we see that H w may be constructed from w in L, which implies P ≤ m L poly-conditioned-SINGULAR.
Proof. Follows from using the quantum walk based Hamiltonian simulation technique of Childs [7,11] to allow the phase estimation of [18,Lemma 19] to be carried out with one-sided error, in the style of [18, Proposition 32], we omit the straightforward details.
We now prove Theorem 2, stated in the introduction, which we restate here for convenience. Proof. Follows from Theorem 41 and a padding argument analogous to that of Theorem 1.
We now prove Theorem 3, stated in the introduction, which we restate here for convenience. Proof. Follows from Theorem 46 and a padding argument analogous to that of Theorem 1.

Well-Conditioned Minimum Eigenvalue and Circuit Trace
In Section 3.1, a "scaled-down" version of the well-conditioned matrix inversion problem was shown to be BQ U L-complete, where the "standard" version of this problem is BQP-complete [20]. We next consider "scaled-down" versions of the minimum eigenvalue problem and of the unitary circuit trace estimation problem, the "standard" versions of which are QMA-complete [24] and DQC1-complete [25,42,44], respectively. Interestingly, the "scaled-down" versions are both BQ U L-complete.
Recall that DQC1 ⊆ BQP ⊆ QMA. It seems reasonable to suspect that both of the preceding inclusions are proper. However, the fact that the "scaled-down" versions of a DQC1-complete problem, a BQP-complete problem, and a QMA-complete are all BQ U L-complete shows that the differences between the time-bounded classes (if these classes are, indeed, different) disappear in the space-bounded setting.
In the following, we say that a function f : f (λ j (H))v j v † j ∈ Herm(n). We use the term L-transducer to refer to a deterministic logspace Turing machine that computes a function. As before, for some unitary circuit Q = (Q 1 , . . . , Q t ), where each Q j ∈ U(n) (i.e., Q j is a unitary gate acting on log n qubits), we also use Q to denote the element Q t · · · Q 1 ∈ U(n) that corresponds to applying the gates Q 1 , . . . , Q t sequentially.
We then study CIRCUITTRACE and FILTEREDMATTRACE. We show that the poly-conditioned versions of both problems are BQ U L-complete. In particular, we show MINEIGENVALUE +,gap ≤ m AC 0 FILTEREDMATTRACE, which, combined with the above results, provides an extremely simple proof of the fact that poly-conditioned-MINEIGENVALUE +,gap , poly-conditioned-MATINV +,≥0 ∈ BQ U L. Note that FILTEREDMATTRACE is a "scaled-down" version of a problem that was shown to be in DQC1 by Cade and Montanaro [10]; their technique has many common elements with the technique used earlier by Harrow, Hassidim, and Lloyd [20] in their proof of the fact that "scaled-up" matrix inversion is in BQP. We use the term "filtered" in reference to the "filter functions" that appear in these proofs.
Proof. Follows straightforwardly from the same technique used in the "standard" proof that the "scaled-up" circuit trace estimation problem is DQC1-complete [25,42,44]; we omit the details.  Proof. By Lemmas 50 and 52, poly-conditioned-FILTEREDMATTRACE is BQ U L-hard. Moreover, poly-conditioned-FILTEREDMATTRACE ∈ BQ U L follows, straightforwardly, from the same technique used to prove [10, Lemma 1] (which shows that a "scaled-up" version of this problem is in DQC1); we omit the details.

Discussion
We conclude by stating a few interesting open problems related to our work. In Theorem 1 we established the equivalence of unitary quantum space, general quantum space, and space-bounded quantum Merlin-Arthur proof systems, in the two-sided bounded-error case. We obtained an analogous equivalence for one-sided unbounded-error in Theorem 3. However, in the case of one-sided bounded-error, we only have the partial results of Theorem 2. In particular, specializing to the case of logspace, we have BQL = BQ U L = QMAL in the two-sided bounded-error case (Theorem 27), and we have RQMAL = RQ U L ⊆ RQL ⊆ coQMAL 1 in the one-sided bounded-error case (Theorem 41). It is naturally to ask if the analogues of results known to hold for two-sided bounded-error also hold for one-sided bounded-error.
By the well-known result of Zachos and Fürer [55], MA = MA 1 ; that is to say, it is possible to achieve perfect completeness for classical (polynomial time) Merlin-Arthur proof systems. On the other hand, the question of whether or not it is possible to achieve perfect completeness for quantum (polynomial time) Merlin-Arthur proof systems (i.e., is QMA = QMA 1 ?) remains open (see, for instance, [1,3,9,22] for previous discussion). We next consider the logspace analogue of this question.
A possible explanation for the difficulty of proving QMA = QMA 1 (if these classes are indeed equal) was provided by Aaronson's result [1] that there is a quantum oracle U such that QMA U = QMA 1 U ; therefore, any proof of QMA = QMA 1 must use a technique that is quantumly nonrelativizing. Note that the technique used by Zachos and Fürer [55] to show MA = MA 1 is (classically) relativizing. It is not hard to see that Aaronson's argument can also be used to produce a quantum oracle U such that QMAL U = QMAL 1 U , and so any proof of QMAL = QMAL 1 must also use quantumly nonrelativizing techniques. We emphasize that the techniques used in this paper to show our results concerning new inclusions between various complexity classes (i.e., the various reductions between linear-algebraic problems shown in this paper) are quantumly nonrelativizing.
Moreover, we note that our paper and that of Boix-Adserà, Eldar, and Mehraban used similar power series techniques to produce space-efficient algorithms for κ(n)-conditioned-DET. However, our quantum algorithm can make use of a power series with an exponentially larger number of terms than seems possible for their (or any other) classical algorithm. This suggests a possible mechanism for explaining the supposed advantage of quantum computers over classical computers in the space-bounded setting. We conclude with a general question.
Open Problem 3. What further relationships can be established between BQL and other natural logspace complexity classes (e.g., #L, GapL, L/poly, etc.)? work tape consisting of s(|w|) = O(log|w|) cells, each of which holds a symbol from some finite alphabet Γ, and (3) a read/write quantum work tape, consisting of s(|w|) = O(log|w|) qubits. Each of the tapes has a single bidirectional head. At the start of the computation, both work-tapes are "blank" (to be precise, each cell of the classical work tape contains some specified blank-symbol in Γ and each qubit of the quantum work tape is in the state |0 ); each qubit of the internal quantum register is also in the state |0 . Each step of the computation of M involves applying a selective quantum operation to the combined register consisting of the internal quantum register and the single qubit that is currently under the head of the quantum work tape; the particular choice of which selective quantum operation to perform may depend on the state of the finite control and the symbols currently under the heads of the input tape and classical work tape. The (classical) result of this quantum operation is stored in the measurement register. Then, depending on this result, as well as on the state of the finite control and the symbols currently under the heads of the input tape and classical work tape, the classical configuration of the machine evolves; to be precise, the state of the finite control is updated, a symbol is written on the classical work-tape, and the head of each work tape moves up to one cell in either direction. The machine accepts (resp.) rejects its input by entering a special (classical) accepting (resp. rejecting state). See [51] for a complete definition.
Proof. Trivially, BQL ⊇ BQ U L. We next show BQL ⊇ BQ U L. Suppose P = (P 1 , P 0 ) ∈ BQL. By definition, there is some QTM M such that the following conditions are satisfied: (1) on any input w ∈ P of length n = |w|, M runs in space at most s(n) = O(log n) (and hence time t(n) = 2 O(s(n)) ), (2) if w ∈ P 1 , then Pr[M accepts w] ≥ 2 3 , and (3) if w ∈ P 0 , then Pr[M accepts w] ≤ 1 3 . Consider running M on some input of length n. At any particular point in time, the configuration of (a single probabilistic branch of) M consists of the current (classical) state of the finite control, the (quantum) contents of the internal quantum register, the (classical) contents of the measurement register, the (classical) positions of the heads on the read only input-tape and the classical and quantum work-tapes, the current (classical) contents of the classical work-tape, and the current (quantum) contents of the quantum work-tape. Let |M | denote the size of the finite control, let b m denote the number of bits of the measurement register, let b q denote the number of qubits of the internal quantum register, and let Γ denote the classical work-tape alphabet. Let C n denote the set of all possible classical configurations of M on inputs of length n, where |C n | = |M |2 bm (n + 2)s(n) 2 |Γ| s(n) = n O (1) . Each classical configuration c ∈ C n corresponds to the element |c in the natural orthonormal basis of the Hilbert space C Cn . Let Q n denote the set of |Q n | = 2 s(n)+bq = n O(1) quantum basis states corresponding to the quantum work-tape and internal quantum register. The contents of the quantum work-tape and the internal quantum register is then described by some |ψ ∈ C Qn . Then each configuration of M on an input of length n corresponds to an element |c |ψ of the Hilbert space H M,n = C Cn ⊗ C Qn . Let d(n) = dim(H M,n ) = |C n ||Q n | = n O(1) .
Consider some input w ∈ P. Let n = |w| denote the length of w, let Φ M,w ∈ Chan(H M,n ) denote the quantum channel that corresponds to a single step of the computation of M on w, and let K(Φ M,w ) ∈ Mat(d 2 (n)) denote the natural representation of Φ M,w . For any t ∈ N, we have Φ t M,w ∈ Chan(H M,n ), which implies σ 1 ((K(Φ M,w )) t ) = σ 1 (K(Φ t M,w )) ≤ d(n) = n O(1) [38, Theorem 1]. Let |ψ n start = |c n start |q n start ∈ H M,n denote the starting configuration of M on an input of length n, where c n start ∈ C n is the classical part of the starting configuration, and |q n start = |0 s(n)+bq ∈ C Qn is the quantum part. Without loss of generality we may, for convenience, assume that M "cleans-up" its workspace at the end of the computation, by returning both its classical and quantum work tapes to the "blank" configuration described above; in particular, this implies that M has a unique accepting configuration |ψ n accept = |c n accept |q n start ∈ H M,n on any input of length n. Let A w = K(Φ M,w ) ∈ Mat(d 2 (n)), x w = vec(|ψ n accept ψ n accept |) ∈ {1, . . . , d 2 (n)}, and y w = vec(|ψ n start ψ n start |) ∈ {1, . . . , d 2 (n)}. Then A t w [x w , y w ] is precisely the probability that M accepts w within t steps.