All reports by Author Zachary Remscrim:

__
TR20-088
| 9th June 2020
__

Bill Fefferman, Zachary Remscrim#### Eliminating Intermediate Measurements in Space-Bounded Quantum Computation

__
TR19-182
| 9th December 2019
__

Zachary Remscrim#### The Limitations of Few Qubits: One-way and Two-way Quantum Finite Automata and the Group Word Problem

Revisions: 1

__
TR19-107
| 29th July 2019
__

Zachary Remscrim#### The Power of a Single Qubit: Two-way Quantum/Classical Finite Automata and the Word Problem for Linear Groups

Revisions: 1

__
TR16-020
| 8th February 2016
__

Zachary Remscrim#### The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling

__
TR13-088
| 16th June 2013
__

Zachary Remscrim, Michael Sipser#### $AC^0$ Pseudorandomness of Natural Operations

Bill Fefferman, Zachary Remscrim

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 ... more >>>

Zachary Remscrim

The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA with only a single-qubit can recognize the language $L_{pal}=\{w \in \{a,b\}^*:w \text{ is ... more >>>

Zachary Remscrim

The two-way quantum/classical finite automaton (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA, with a single qubit, can recognize, with one-sided bounded-error, the language $L_{eq}=\{a^m b^m |m \in \mathbb{N}\}$ in ... more >>>

Zachary Remscrim

In this paper, we apply tools from algebraic geometry to prove new results concerning extractors for algebraic sets, the recursive Fourier sampling problem, and VC dimension. We present a new construction of an extractor which works for algebraic sets defined by polynomials over $\mathbb{F}_2$ of substantially higher degree than the ... more >>>

Zachary Remscrim, Michael Sipser

A function $f:\Sigma^{*} \rightarrow \Sigma^{*}$ on strings is $AC^0$-pseudorandom if the pair $(x,\hat f(x))$ is $AC^0$-indistinguishable from a uniformly random pair $(y,z)$ when $x$ is chosen uniformly at random. Here $\hat f(x)$ is the string that is obtained from $f(x)$ by discarding some selected bits from $f(x)$.

It is shown ... more >>>