publications | Luke Schaeffer

2024

Trading T-gates for dirty qubits in state preparation and unitary synthesis

Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer

Quantum, Jun 2024

Appeared in QIP 2020.

Abs DOI arXiv

Efficient synthesis of arbitrary quantum states and unitaries from a universal fault-tolerant gate-set e.g. Clifford+T is a key subroutine in quantum computation. As large quantum algorithms feature many qubits that encode coherent quantum information but remain idle for parts of the computation, these should be used if it minimizes overall gate counts, especially that of the expensive T-gates. We present a quantum algorithm for preparing any dimension-N pure quantum state specified by a list of N classical numbers, that realizes a trade-off between space and T-gates. Our scheme uses O(log(N/ϵ)) clean qubits and a tunable number of ∼(λlog(log(N)/ϵ)) dirty qubits, to reduce the T-gate cost to O(N/λ+λlog(N/ϵ) log((log N)/ϵ)). This trade-off is optimal up to logarithmic factors, proven through an unconditional gate counting lower bound, and is, in the best case, a quadratic improvement in T-count over prior ancillary-free approaches. We prove similar statements for unitary synthesis by reduction to state preparation. Underlying our constructions is a T-efficient circuit implementation of a quantum oracle for arbitrary classical data.
Fast simulation of planar Clifford circuits

David Gosset, Daniel Grier, Alex Kerzner, and Luke Schaeffer

Quantum, Sep 2024

Appeared in QIP 2021.

Abs DOI arXiv

A general quantum circuit can be simulated classically in exponential time. If it has a planar layout, then a tensor-network contraction algorithm due to Markov and Shi has a runtime exponential in the square root of its size, or more generally exponential in the treewidth of the underlying graph. Separately, Gottesman and Knill showed that if all gates are restricted to be Clifford, then there is a polynomial time simulation. We combine these two ideas and show that treewidth and planarity can be exploited to improve Clifford circuit simulation. Our main result is a classical algorithm with runtime scaling asymptotically as n^(ω/2) < n^1.19 which samples from the output distribution obtained by measuring all n qubits of a planar graph state in given Pauli bases. Here ω is the matrix multiplication exponent. We also provide a classical algorithm with the same asymptotic runtime which samples from the output distribution of any constant-depth Clifford circuit in a planar geometry. Our work improves known classical algorithms with cubic runtime. A key ingredient is a mapping which, given a tree decomposition of some graph G, produces a Clifford circuit with a structure that mirrors the tree decomposition and which emulates measurement of the corresponding graph state. We provide a classical simulation of this circuit with the runtime stated above for planar graphs and otherwise nt^(ω−1) where t is the width of the tree decomposition. Our algorithm incorporates two subroutines which may be of independent interest. The first is a matrix-multiplication-time version of the Gottesman-Knill simulation of multi-qubit measurement on stabilizer states. The second is a new classical algorithm for solving symmetric linear systems over F_2 in a planar geometry, extending previous works which only applied to non-singular linear systems in the analogous setting.
Succinct Fermion Data Structures

Joseph Carolan, and Luke Schaeffer

Sep 2024

Abs arXiv

Simulating fermionic systems on a quantum computer requires representing fermionic states using qubits. The complexity of many simulation algorithms depends on the complexity of implementing rotations generated by fermionic creation-annihilation operators, and the space depends on the number of qubits used. While standard fermion encodings like Jordan-Wigner are space optimal for arbitrary fermionic systems, physical symmetries like particle conservation can reduce the number of physical configurations, allowing improved space complexity. Such space saving is only feasible if the gate overhead is small, suggesting a (quantum) data structures problem, wherein one would like to minimize space used to represent a fermionic state, while still enabling efficient rotations. We define a structure which naturally captures mappings from fermions to systems of qubits. We then instantiate it in two ways, giving rise to two new second-quantized fermion encodings of F fermions in M modes. An information theoretic minimum of I:=⌈log((M choose F))⌉ qubits is required for such systems, a bound we nearly match over the entire parameter regime. (1) Our first construction uses I+o(I) qubits when F=o(M), and allows rotations generated by creation-annihilation operators in O(I) gates and O(log(M) loglog(M)) depth. (2) Our second construction uses I+O(1) qubits when F=Θ(M), and allows rotations generated by creation-annihilation operators in O(I^3) gates. In relation to comparable prior work, the first represents a polynomial improvement in both space and gate complexity (against Kirby et al. 2022), and the second represents an exponential improvement in gate complexity at the cost of only a constant number of additional qubits (against Harrison et al. or Shee et al. 2022), in the described parameter regimes.

2023

On the Rational Degree of Boolean Functions and Applications

Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak M. Kumar, Luke Schaeffer, Daochen Wang, and Michael Whitmeyer

Sep 2023

Abs DOI arXiv

We study a natural complexity measure of Boolean functions known as the (exact) rational degree. For total functions f, it is conjectured that rdeg(f) is polynomially related to deg(f), where deg(f) is the Fourier degree. Towards this conjecture, we show that symmetric functions have rational degree at least deg(f)/2 and monotone functions have rational degree at least sqrt(deg(f)). We observe that both of these lower bounds are tight. In addition, we show that all read-once depth-d Boolean formulae have rational degree at least Ω(deg(f)^(1/d)). Furthermore, we show that almost every Boolean function on n variables has rational degree at least n/2−O(sqrt(n)). In contrast to total functions, we exhibit partial functions that witness unbounded separations between rational and approximate degree, in both directions. As a consequence, we show that for quantum computers, post-selection and bounded-error are incomparable resources in the black-box model.
The first-order theory of binary overlap-free words is decidable

Luke Schaeffer, and Jeffrey Shallit

Canadian Journal of Mathematics, Sep 2023

Abs DOI arXiv

We show that the first-order logical theory of the binary overlap-free words (and, more generally, the α-free words for rational α, 2<α≤7/3), is decidable. As a consequence, many results previously obtained about this class through tedious case- based proofs can now be proved "automatically", using a decision procedure.

2022

The Classification of Clifford Gates over Qubits

Daniel Grier, and Luke Schaeffer

Quantum, Sep 2022

Presented in QIP 2018

Abs DOI arXiv

We examine the following problem: given a collection of Clifford gates, describe the set of unitaries generated by circuits composed of those gates. Specifically, we allow the standard circuit operations of composition and tensor product, as well as ancillary workspace qubits as long as they start and end in states uncorrelated with the input, which rule out common "magic state injection" techniques that make Clifford circuits universal. We show that there are exactly 57 classes of Clifford unitaries and present a full classification characterizing the gate sets which generate them. This is the first attempt at a quantum extension of the classification of reversible classical gates introduced by Aaronson et al., another part of an ambitious program to classify all quantum gate sets. The classification uses, at its center, a reinterpretation of the tableau representation of Clifford gates to give circuit decompositions, from which elementary generators can easily be extracted. The 57 different classes are generated in this way, 30 of which arise from the single-qubit subgroups of the Clifford group. At a high level, the remaining classes are arranged according to the bases they preserve. For instance, the CNOT gate preserves the X and Z bases because it maps X-basis elements to X-basis elements and Z-basis elements to Z-basis elements. The remaining classes are characterized by more subtle tableau invariants; for instance, the T_4 and phase gate generate a proper subclass of Z-preserving gates.
Sample-optimal classical shadows for pure states

Daniel Grier, Hakop Pashayan, and Luke Schaeffer

Sep 2022

Presented in TQC 2022.

Abs DOI arXiv

We consider the classical shadows task for pure states in the setting of both joint and independent measurements. The task is to measure few copies of an unknown pure state ρ in order to learn a classical description which suffices to later estimate expectation values of observables. Specifically, the goal is to approximate Tr(Oρ) for any Hermitian observable O to within additive error ϵ provided Tr(O^2)≤B and ||O||=1. Our main result applies to the joint measurement setting, where we show Θ(sqrt(B)/ϵ−1/ϵ^2) samples of ρ are necessary and sufficient to succeed with high probability. The upper bound is a quadratic improvement on the previous best sample complexity known for this problem. For the lower bound, we see that the bottleneck is not how fast we can learn the state but rather how much any classical description of ρ can be compressed for observable estimation. In the independent measurement setting, we show that O(sqrt(Bd)/ϵ−1/ϵ^2) samples suffice. Notably, this implies that the random Clifford measurements algorithm of Huang, Kueng, and Preskill, which is sample-optimal for mixed states, is not optimal for pure states. Interestingly, our result also uses the same random Clifford measurements but employs a different estimator.

2021

Ostrowski-automatic sequences: Theory and applications

Aseem R. Baranwal, Luke Schaeffer, and Jeffrey O. Shallit

Theor. Comput. Sci., Sep 2021

Abs DOI

We extend the notion of k-automatic sequences to Ostrowski-automatic sequences, and develop a procedure to computationally decide certain combinatorial and enumeration questions about such sequences that can be expressed as predicates in first-order logic. Our primary contribution is the design and implementation of an adder recognizing addition in a generalized Ostrowski numeration system. We also provide applications of our work to several topics in combinatorics on words, including repetitions and pattern avoidance. We partially resolve a previous conjecture about balanced words by Rampersad et al., and make the first progress on an open problem on rich words by Vesti. We also prove some known results about Lucas words using only machine computation.
Decidability for Sturmian words

Philipp Hieronymi, Dun Ma, Reed Oei, Luke Schaeffer, Christian Schulz, and Jeffrey O. Shallit

Sep 2021

Appeared in CSL 2022.

Abs DOI arXiv

We show that the first-order theory of Sturmian words over Presburger arithmetic is decidable. Using a general adder recognizing addition in Ostrowski numeration systems by Baranwal, Schaeffer and Shallit, we prove that the first-order expansions of Presburger arithmetic by a single Sturmian word are uniformly ω-automatic, and then deduce the decidability of the theory of the class of such structures. Using an implementation of this decision algorithm called Pecan, we automatically reprove classical theorems about Sturmian words in seconds, and are able to obtain new results about antisquares and antipalindromes in characteristic Sturmian words.
Interactive quantum advantage with noisy, shallow Clifford circuits

Daniel Grier, Nathan Ju, and Luke Schaeffer

Feb 2021

Appeared in QIP 2021.

Abs arXiv

Recent work by Bravyi et al. constructs a relation problem that a noisy constant-depth quantum circuit (QNC^0) can solve with near certainty (probability 1−o(1)), but that any bounded fan-in constant-depth classical circuit (NC^0) fails with some constant probability. We show that this robustness to noise can be achieved in the other low-depth quantum/classical circuit separations in this area. In particular, we show a general strategy for adding noise tolerance to the interactive protocols of Grier and Schaeffer. As a consequence, we obtain an unconditional separation between noisy QNC^0 circuits and AC^0[p] circuits for all primes p≥2, and a conditional separation between noisy QNC^0 circuits and log-space classical machines under a plausible complexity-theoretic conjecture. A key component of this reduction is showing average-case hardness for the classical simulation tasks – that is, showing that a classical simulation of the quantum interactive task is still powerful even if it is allowed to err with constant probability over a uniformly random input. We show that is true even for quantum tasks which are parity-L-hard to simulate. To do this, we borrow techniques from randomized encodings used in cryptography.
Classical algorithms for Forrelation

Sergey Bravyi, David Gosset, Daniel Grier, and Luke Schaeffer

Feb 2021

Appeared in QIP 2022.

Abs arXiv

We study the forrelation problem: given a pair of n-bit Boolean functions f and g, estimate the correlation between f and the Fourier transform of g. This problem is known to provide the largest possible quantum speedup in terms of its query complexity and achieves the landmark oracle separation between the complexity class BQP and the Polynomial Hierarchy. Our first result is a classical algorithm for the forrelation problem which has runtime O(n2^(n/2)). This is a nearly quadratic improvement over the best previously known algorithm. Secondly, we show that quantum query algorithm that makes t queries to an n-bit oracle can be simulated by classical query algorithm making only O(2^(n(1−1/2t))) queries. This fixes a gap in the literature arising from a recently discovered critical error in a previous proof; it matches recently established lower bounds (up to poly(n,t)) factors) and thus characterizes the maximal separation in query complexity between quantum and classical algorithms. Finally, we introduce a graph-based forrelation problem where n binary variables live at vertices of some fixed graph and the functions f,g are products of terms describing interactions between nearest-neighbor variables. We show that the graph-based forrelation problem can be solved on a classical computer in time O(n) for any bipartite graph, any planar graph, or, more generally, any graph which can be partitioned into two subgraphs of constant treewidth. The graph-based forrelation is simply related to the variational energy achieved by the Quantum Approximate Optimization Algorithm (QAOA) with two entangling layers and Ising-type cost functions. By exploiting the connection between QAOA and the graph-based forrelation we were able to simulate the recently proposed Recursive QAOA with two entangling layers and 225 qubits on a laptop computer.
String Attractors for Automatic Sequences

Luke Schaeffer, and Jeffrey Shallit

Feb 2021

Abs arXiv

We show that it is decidable, given an automatic sequence s and a constant c, whether all prefixes of s have a string attractor of size ≤c. Using a decision procedure based on this result, we show that all prefixes of the period-doubling sequence of length ≥2 have a string attractor of size 2. We also prove analogous results for other sequences, including the Thue-Morse sequence and the Tribonacci sequence. We also provide general upper and lower bounds on string attractor size for different kinds of sequences. For example, if s has a finite appearance constant, then there is a string attractor for s[0..n−1] of size O(log n). If further s is linearly recurrent, then there is a string attractor for s[0..n−1] of size O(1). For automatic sequences, the size of the smallest string attractor for s[0..n−1] is either Θ(1) or Θ(log n), and it is decidable which case occurs. Finally, we close with some remarks about greedy string attractors.

2020

Interactive shallow Clifford circuits: quantum advantage against NC^1 and beyond

Daniel Grier, and Luke Schaeffer

Nov 2020

Presented in STOC 2020, appeared in QIP 2020.

Abs DOI arXiv

Recent work of Bravyi et al. and follow-up work by Bene Watts et al. demonstrates a quantum advantage for shallow circuits: constant-depth quantum circuits can perform a task which constant-depth classical (i.e., AC^0) circuits cannot. Their results have the advantage that the quantum circuit is fairly practical, and their proofs are free of hardness assumptions (e.g., factoring is classically hard, etc.). Unfortunately, constant-depth classical circuits are too weak to yield a convincing real-world demonstration of quantum advantage. We attempt to hold on to the advantages of the above results, while increasing the power of the classical model. Our main result is a two-round interactive task which is solved by a constant-depth quantum circuit (using only Clifford gates, between neighboring qubits of a 2D grid, with Pauli measurements), but such that any classical solution would necessarily solve parity-L-hard problems. This implies a more powerful class of constant-depth classical circuits (e.g., AC^0[p] for any prime p) unconditionally cannot perform the task. Furthermore, under standard complexity-theoretic conjectures, log-depth circuits and log-space Turing machines cannot perform the task either. Using the same techniques, we prove hardness results for weaker complexity classes under more restrictive circuit topologies. Specifically, we give QNC0 interactive tasks on 2×n and 1×n grids which require classical simulations of power NC^1 and AC^0[6], respectively. Moreover, these hardness results are robust to a small constant fraction of error in the classical simulation. We use ideas and techniques from the theory of branching programs, quantum contextuality, measurement-based quantum computation, and Kilian randomization.

2019

Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal

Jun 2019

Presented in QIP 2019, appeared in STOC 2019.

Abs DOI arXiv

Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). In other words, they exhibited a search problem in QNC^0 that is not in NC^0. We strengthen their result by proving that the 2D HLF problem is not contained in AC^0, the class of classical, polynomial-size, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates. We also supplement this worst-case lower bound with an average-case result: There exists a simple distribution under which any AC^0 circuit (even of nearly exponential size) has exponentially small correlation with the 2D HLF problem. Our results are shown by constructing a new problem in QNC^0, which we call the Relaxed Parity Halving Problem, which is easier to work with. We prove our AC^0 lower bounds for this problem, and then show that it reduces to the 2D HLF problem. As a step towards even stronger lower bounds, we present a search problem that we call the Parity Bending Problem, which is in QNC^0/qpoly (QNC^0 circuits that are allowed to start with a quantum state of their choice that is independent of the input), but is not even in AC^0[2] (the class AC^0 with unbounded fan-in XOR gates). All the quantum circuits in our paper are simple, and the main difficulty lies in proving the classical lower bounds. For this we employ a host of techniques, including a refinement of Håstad’s switching lemmas for multi-output circuits that may be of independent interest, the Razborov-Smolensky AC^0[2] lower bound, Vazirani’s XOR lemma, and lower bounds for non-local games.
A Note on Key Agreement and Non-Interactive Commitments

Alex Lombardi, and Luke Schaeffer

IACR Cryptol. ePrint Arch., Mar 2019

Abs

We observe that any key agreement protocol satisfying perfect completeness, regardless of its round complexity, can be used to construct a non-interactive commitment scheme. This observation simplifies the cryptographic assumptions required for some protocols that utilize non-interactive commitments and removes the need for ad-hoc constructions of non-interactive commitments from specific assumptions such as Learning with Errors.

2018

A Quantum Query Complexity Trichotomy for Regular Languages

Scott Aaronson, Daniel Grier, and Luke Schaeffer

Dec 2018

Appeared in QIP 2019 and FOCS 2019.

Abs DOI arXiv

We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity Θ(1), Θ(sqrt(n)), or Θ(n). The extreme uniformity of regular languages prevents them from taking any other asymptotic complexity. This is in contrast to even the context-free languages, which we show can have query complexity Θ(nc) for all computable c ∈ [1/2, 1]. Our result implies an equivalent trichotomy for the approximate degree of regular languages, and a dichotomy—either Θ(1) or Θ(n)—for sensitivity, block sensitivity, certificate complexity, deterministic query complexity, and randomized query complexity. The heart of the classification theorem is an explicit quantum algorithm which decides membership in any star-free language in ˜O(sqrt(n)) time. This well-studied family of the regu- lar languages admits many interesting characterizations, for instance, as those languages ex- pressible as sentences in first-order logic over the natural numbers with the less-than relation. Therefore, not only do the star-free languages capture functions such as OR, they can also ex- press functions such as "there exist a pair of 2’s such that everything between them is a 0." Thus, we view the algorithm for star-free languages as a nontrivial generalization of Grover’s algorithm which extends the quantum quadratic speedup to a much wider range of string-processing algorithms than was previously known. We show applications to problems such as evaluating dynamic constant-depth Boolean formulas and recognizing balanced parentheses nested constantly many levels deep.
New Hardness Results for the Permanent Using Linear Optics

Daniel Grier, and Luke Schaeffer

Oct 2018

Appeared in CCC 2018.

Abs DOI arXiv

In 2011, Aaronson gave a striking proof, based on quantum linear optics, that the problem of computing the permanent of a matrix is #P-hard. Aaronson’s proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant’s seminal proof of the same fact in 1979. Nevertheless, it did not show #P-hardness of the permanent for any class of matrices which was not previously known. In this paper, we present a collection of new results about matrix permanents that are derived primarily via these linear optical techniques. First, we show that the problem of computing the permanent of a real orthogonal matrix is #P-hard. Much like Aaronson’s original proof, this implies that even a multiplicative approximation remains #P-hard to compute. The hardness result even translates to permanents of orthogonal matrices over the finite field F_p^4 for p != 2, 3. Interestingly, this characterization is tight: in fields of characteristic 2, the permanent coincides with the determinant; in fields of characteristic 3, one can efficiently compute the permanent of an orthogonal matrix by a nontrivial result of Kogan. Finally, we use more elementary arguments to prove #P-hardness for the permanent of a positive semidefinite matrix. This result shows that certain probabilities of boson sampling experiments with thermal states are hard to compute exactly, despite the fact that they can be efficiently sampled by a classical computer.

2017

Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability

Chen Fei Du, Hamoon Mousavi, Eric Rowland, Luke Schaeffer, and Jeffrey O. Shallit

Theor. Comput. Sci., Oct 2017

Abs DOI arXiv

We use a decision procedure for the "Fibonacci-automatic" words to solve problems about a number of different sequences. In particular, we prove that there exists an aperiodic infinite binary word avoiding the pattern xxx^R. This is the first avoidability result concerning a nonuniform morphism proven purely mechanically.

2016

Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties

Chen Fei Du, Hamoon Mousavi, Luke Schaeffer, and Jeffrey O. Shallit

Int. J. Found. Comput. Sci., Oct 2016

Abs DOI arXiv

We continue our study of the class of Fibonacci-automatic words. These are infinite words whose nth term is defined in terms of a finite-state function of the Fibonacci representation of n. In this paper, we show how enumeration questions (such as counting the number of squares of length n in the Fibonacci word) can be decided purely mechanically, using a decision procedure. We reprove some known results, in a unified way, using our technique, and we prove some new results. We also examine abelian properties of these words. As a consequence of our results on abelian properties, we get the result that every nontrivial morphic image of the Fibonacci word is Fibonacci-automatic.
Decision algorithms for Fibonacci-automatic Words, I: Basic results

Hamoon Mousavi, Luke Schaeffer, and Jeffrey O. Shallit

RAIRO Theor. Informatics Appl., Oct 2016

Abs DOI arXiv

We implement a decision procedure for answering questions about a class of infinite words that might be called (for lack of a better name) "Fibonacci-automatic". This class includes, for example, the famous Fibonacci word f = f_0 f_1 f_2··· = 01001010··· , the fixed point of the morphism 0 → 01 and 1 → 0. We then recover many results about the Fibonacci word from the literature (and improve some of them), such as assertions about the occurrences in f of squares, cubes, palindromes, and so forth.
Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences

Luke Schaeffer, and Jeffrey O. Shallit

Electron. J. Comb., Feb 2016

Abs DOI arXiv

We prove that the property of being closed (resp., palindromic, rich, privileged trapezoidal, balanced) is expressible in first-order logic for automatic (and some related) sequences. It therefore follows that the characteristic function of those n for which an automatic sequence x has a closed (resp., palindromic, privileged, rich, trapezoidal, balanced) factor of length n is itself automatic. For privileged words this requires a new characterization of the privileged property. We compute the corresponding characteristic functions for various famous sequences, such as the Thue-Morse sequence, the Rudin-Shapiro sequence, the ordinary paperfolding sequence, the period-doubling sequence, and the Fibonacci sequence. Finally, we also show that the function counting the total number of palindromic factors in the prefix of length n of a k-automatic sequence is not k-synchronized.

2015

A New Approach to the Paperfolding Sequences

Daniel Goč, Hamoon Mousavi, Luke Schaeffer, and Jeffrey O. Shallit

Feb 2015

Presented at CiE 2015.

Abs DOI

In this paper we show how to re-derive known results about the paperfolding sequences, and obtain new ones, using a new approach using a decision method and some machine computation. We also obtain exact expressions for the recurrence and appearance function of the paperfolding sequences, and solve an open problem of Rampersad about factors shared in common between two different paperfolding sequences.
The Classification of Reversible Bit Operations

Scott Aaronson, Daniel Grier, and Luke Schaeffer

Apr 2015

Appeared in ITCS 2017

Abs DOI arXiv

We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post’s lattice, a central result in mathematical logic from the 1940s. It is a step toward the ambitious goal of classifying all possible quantum gate sets acting on qubits. Our theorem implies a linear-time algorithm (which we have implemented), that takes as input the truth tables of reversible gates G and H, and that decides whether G generates H. Previously, this problem was not even known to be decidable. The theorem also implies that any n-bit reversible circuit can be "compressed" to an equivalent circuit, over the same gates, that uses at most 2^n*poly(n) gates and O(1) ancilla bits; these are the first upper bounds on these quantities known, and are close to optimal. Finally, the theorem implies that every non-degenerate reversible gate can implement either every reversible transformation, or every affine transformation, when restricted to an "encoded subspace." Briefly, the theorem says that every set of reversible gates generates either all reversible transformations on n-bit strings (as the Toffoli gate does); no transformations; all transformations that preserve Hamming weight (as the Fredkin gate does); all transformations that preserve Hamming weight mod k for some k; all affine transformations (as the Controlled-NOT gate does); all affine transformations that preserve Hamming weight mod 2 or mod 4, inner products mod 2, or a combination thereof; or a previous class augmented by a NOT or NOTNOT gate. Ruling out the possibility of additional classes, not in the list, requires some arguments about polynomials, lattices, and Diophantine equations.
A Physically Universal Quantum Cellular Automaton

Luke Schaeffer

Jun 2015

Presented in AUTOMATA 2015

DOI
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games

Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, and Thomas Thierauf

In Algorithms and Computation, Feb 2015

Appeared in ISAAC 2015.

Abs DOI

A black-white combinatorial game is a two-person game in which the pieces are colored either black or white. The players alternate moving or taking elements of a specific color designated to them before the game begins. A player loses the game if there is no legal move available for his color on his turn.

2014

Avoiding Three Consecutive Blocks of the Same Size and Same Sum

Julien Cassaigne, James D. Currie, Luke Schaeffer, and Jeffrey Shallit

J. ACM, Apr 2014

Abs DOI arXiv

We show that there exists an infinite word over the alphabet 0, 1, 3, 4 containing no three consecutive blocks of the same size and the same sum. This answers an open problem of Pirillo and Varricchio from 1994.
A Physically Universal Cellular Automaton

Luke Schaeffer

Electronic Colloquium on Computational Complexity (ECCC), Jun 2014

Best Student Paper in ITCS 2015.

Abs DOI

Several cellular automata (CA) are known to be universal in the sense that one can simulate arbitrary computations (e.g., circuits or Turing machines) by carefully encoding the computational device and its input into the cells of the CA. In this paper, we consider a different kind of universality proposed by Janzing. A cellular automaton is physically universal if it is possible to implement any transformation on a finite region of the CA by initializing the complement of the region and letting the system evolve. We give the first known example of a physically universal CA, answering an open problem of Janzing and opening the way for further research in this area.

2013

Ostrowski Numeration and the Local Period of Sturmian Words

Luke Schaeffer

Jun 2013

Presented in LATA 2013.

Abs DOI arXiv

We show that the local period at position n in a characteristic Sturmian word can be given in terms of the Ostrowski representation for n + 1.
Subword Complexity and k-Synchronization

Daniel Goč, Luke Schaeffer, and Jeffrey Shallit

In Developments in Language Theory, Jun 2013

Appeared in DLT 2013.

Abs DOI arXiv

We show that the subword complexity function ρ_x(n), which counts the number of distinct factors of length n of a sequence x, is k-synchronized in the sense of Carpi if x is k-automatic. As an application, we generalize recent results of Goldstein. We give analogous results for the number of distinct factors of length n that are primitive words or powers. In contrast, we show that the function that counts the number of unbordered factors of length n is not necessarily k-synchronized for k-automatic sequences.

2012

The Critical Exponent is Computable for Automatic Sequences

Luke Schaeffer, and Jeffrey Shallit

International Journal of Foundations of Computer Science, Jun 2012

Abs DOI arXiv

The critical exponent of an infinite word is defined to be the supremum of the exponent of each of its factors. For k-automatic sequences, we show that this critical exponent is always either a rational number or infinite, and its value is computable. Our results also apply to variants of the critical exponent, such as the initial critical exponent of Berthé, Holton, and Zamboni and the Diophantine exponent of Adamczewski and Bugeaud. Our work generalizes or recovers previous results of Krieger and others, and is applicable to other situations; e.g., the computation of the optimal recurrence constant for a linearly recurrent k-automatic sequence.
An Improved Lower Bound for Stack Sorting

Luke Schaeffer

Dec 2012

Abs DOI arXiv

We consider the problem of sorting elements on a series of stacks, introduced by Tarjan and Knuth. We improve the asymptotic lower bound for the number of stacks necessary to sort n elements to 0.561 log_2(n)+O(1). This is the first significant improvement since the previous lower bound, 0.5 log_2(n)+O(1), was established by Knuth in 1972.

2011

Decidability and Shortest Strings in Formal Languages

Levent Alpoge, Thomas Ang, Luke Schaeffer, and Jeffrey Shallit

Dec 2011

Appeared in DCFS 2011.

Abs DOI arXiv

Given a formal language L specified in various ways, we consider the problem of determining if L is nonempty. If L is indeed nonempty, we find upper and lower bounds on the length of the shortest string in L.