There are a number of questions in quantum complexity that have been resolved in the time-bounded setting, but remain open in the space-bounded setting. For example, it is not currently known if space-bounded probabilistic computations can be simulated by space-bounded quantum machines without allowing measurements during the computation, while it is known that an analogous statement holds in the time-bounded case. A more general question asks if measurements during a quantum computation can allow for more space-efficient solutions to certain problems. In this paper we show that space-bounded quantum Turing machines can efficiently simulate a limited class of random processes-random walks on undirected graphs-without relying on measurements during the computation. By means of such simulations, it is demonstrated that the undirected graph connectivity problem for regular graphs can be solved by one-sided error quantum Turing machines that run in logspace and require a single measurement at the end of their computations. It follows that symmetric logspace is contained in the quantum analogue of randomized logspace, i.e., SL/spl sube/QR/sub H/L.
There are a number of questions in quantum complexity that have been resolved in the time-bounded setting, but remain open in the space-bounded setting. For example, it is not currently known if space-bounded probabilistic computations can be simulated by space-bounded quantum machines without allowing measurements during the computation, while it is known that an analogous statement holds in the time-bounded case. A more general question asks if measurements during a quantum computation can allow for more space-efficient solutions to certain problems. In this paper we show that space-bounded quantum Turing machines can efficiently simulate a limited class of random processes-random walks on undirected graphs-without relying on measurements during the computation. By means of such simulations, it is demonstrated that the undirected graph connectivity problem for regular graphs can be solved by one-sided error quantum Turing machines that run in logspace and require a single measurement at the end of their computations. It follows that symmetric logspace is contained in the quantum analogue of randomized logspace, i.e., SL/spl sube/QR/sub H/L.
It is not currently known if quantum Turing machines can efficiently simulate probabilistic computations in the space-bounded case. In this paper we show that space-bounded quantum Turing machines can efficiently simulate a limited class of random processes: random walks on undirected graphs. By means of such simulations, it is demonstrated that the undirected graph connectivity problem for regular graphs can be solved by one-sided error quantum Turing machines that run in logspace and halt absolutely. It follows that symmetric logspace is contained in the quantum analogue of randomized logspace.
In this dissertation, we investigate the computational power of quantum Turing machines operating in bounded space. First, we consider space-bounds that are space-constructible and at least logarithmic in the input size. For such space-bounds, it is shown that quantum Turing machines and probabilistic Turing machines are equivalent in power in the unbounded-error setting, in the sense that each model may simulate the other with at most a constant factor increase in space. From this, it follows that any quantum Turing machine computation can be simulated deterministically with at most a quadratic increase in space, and can be simulated deterministically in time at most exponential in the space-bound. Several other facts regarding quantum complexity classes defined in terms of such space-bounds are also proved. Second, we consider the power of quantum Turing machines restricted to constant space. In this case, we first prove that quantum Turing machines having one-sided error and running in linear time are strictly more powerful than probabilistic Turing machines having either one-sided error or having two-sided bounded error and running in polynomial time. Second, we prove that exact (i.e., accepting with probability 0 or 1) constant-space quantum Turing machines upon which no restrictions on running time are placed can recognize languages that cannot be recognized by any bounded-error constant-space probabilistic Turing machine. ii Acknowledgements I would like to take this opportunity to express my gratitude to a number of people. First, I would like to thank my advisor Eric Bach for all that he has taught me, regarding both theoretical computer science and how to be a researcher in general. His advice and support are greatly appreciated. I would also like to thank Anne Condon for her great advice and for many helpful discussions during my years as a graduate student. This dissertation has benefitted greatly from comments and suggestions by Anne and Eric as well.
This paper investigates the relative power of space-bounded quantum and classical (probabilistic) computational models. The following relationships are proved. 1. Any probabilistic Turing machine (PTM) which runs in space s and which halts absolutely (i.e. halts with certainty after a finite number of steps) can be simulated in space O(s) by a quantum Turing machine (QTM). If the PTM operates with bounded error, then the QTM may be taken to operate with bounded error as well, although the QTM may not halt absolutely in this case. In the unbounded error case, the QTM may be taken to halt absolutely. 2. Any QTM running in space s can be simulated by an unbounded error PTM running in space O(s). No assumptions on the probability of error or Turing time for the QTM are required, but it is assumed that all transition amplitudes of the quantum machine are rational. It follows that unbounded error, space O(s) bounded quantum Turing machines and probabilistic Turing machines are equivalent in power. This implies that any space s QTM can be simulated deterministically in space O(s/sup 2/), and further that any (unbounded-error) QTM running in log-space can be simulated in NC/sup 2/ We also consider quantum analogues of nondeterministic and one-sided error probabilistic space-bounded classes, and prove some simple relationships regarding these classes.
We define a class of stochastic processes based on evolutions and measurements of quantum systems, and consider the complexity of predicting their long term behavior. It is shown that a very general class of decision problems regarding these stochastic processes can be efficiently solved classically in the space-bounded case. The following corollaries are implied by our main result for any space-constructible space bound s satisfying s(n)=/spl Omega/(log n): (i) any space O(s) uniform family of quantum circuit acting on s qubits and consisting of unitary gates and measurement gates defined in a typical way by matrices of algebraic numbers can be simulated by an unbounded error space O(s) ordinary (i.e., fair-coin flipping) probabilistic Turing machine, and hence by space O(s) uniform classical (deterministic) circuits of depth O(s/sup 2/) and size 2/sup 0/(s); (2) any quantum Turing machine running in space s, having arbitrary algebraic transition amplitudes, allowing unrestricted measurements during its computation, and having no restrictions on running time can be simulated by a space O(s) ordinary probabilistic Turing machine in the unbounded error setting. We also obtain the following classical result: any unbounded error probabilistic Turing machine running in space s that allows algebraic probabilities and algebraic cut-point can be simulated by a space O(s) ordinarily probabilistic Turing machine with cut-point 1/2. Our technique for handling algebraic numbers in the above simulations may be of independent interest. It is shown that any real algebraic number can be accurately approximated by a ratio of GapL functions.
This thesis studies space-bounded quantum computation, focusing on quantum algorithms in settings where memory is limited. The central goal is to understand which quantum advantages persist under such constraints and how quantum resources affect classical time-space tradeoffs. The thesis approaches these questions through st-connectivity, a central problem in space complexity theory. We develop quantum algorithms and tradeoff results for both undirected and directed st-connectivity. In the undirected case, we show that quantum algorithms can achieve near-optimal time using only logarithmic space, in contrast to classical algorithms, which exhibit nontrivial time-space tradeoffs. This demonstrates a fundamental difference between classical and quantum computation in memory-constrained regimes. For directed st-connectivity, we establish the first nontrivial quantum time–space tradeoff. This problem is more challenging, as techniques such as quantum walks and reversibility do not directly apply. We show that quantum computation can improve upon known classical tradeoff bounds even when only a small quantum workspace is available. A key contribution of the thesis is a compositional framework for quantum algorithms based on multidimensional quantum walks. We introduce subspace graphs, an abstract model that enables modular design and efficient recursion without the overheads that typically slow down recursive quantum algorithms. Finally, we extend undirected st-connectivity to unitary-labeled graphs, where edges represent quantum transformations. We present an efficient quantum algorithm for this generalized connectivity problem. Together, these results advance the understanding of space-bounded quantum computation and quantum time-space tradeoffs.
Space complexity is a key field of study in theoretical computer science. In the quantum setting there are clear motivations to understand the power of space-restricted computation, as qubits are an especially precious and limited resource. Recently, a new branch of space-bounded complexity called catalytic computing has shown that reusing space is a very powerful computational resource, especially for subroutines that incur little to no space overhead. While quantum catalysis in an information theoretic context, and the power of "dirty" qubits for quantum computation, has been studied over the years, these models are generally not suitable for use in quantum space-bounded algorithms, as they either rely on specific catalytic states or destroy the memory being borrowed. We define the notion of catalytic computing in the quantum setting and show a number of initial results about the model. First, we show that quantum catalytic logspace can always be computed quantumly in polynomial time; the classical analogue of this is the largest open question in catalytic computing. This also allows quantum catalytic space to be defined in an equivalent way with respect to circuits instead of Turing machines. We also prove that quantum catalytic logspace can simulate log-depth threshold circuits, a class which is known to contain (and believed to strictly contain) quantum logspace, thus showcasing the power of quantum catalytic space. Finally we show that both unitary quantum catalytic logspace and classical catalytic logspace can be simulated in the one-clean qubit model.