Arrow Research search

Author name cluster

Eric Bach 0001

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers
1 author row

Possible papers

8

STOC Conference 2001 Conference Paper

One-dimensional quantum walks

  • Andris Ambainis
  • Eric Bach 0001
  • Ashwin Nayak 0001
  • Ashvin Vishwanath
  • John Watrous

We define and analyze quantum computational variants of random walks on one-dimensional lattices. In particular, we analyze a quantum analog of the symmetric random walk, which we call the Hadamard walk . Several striking differences between the quantum and classical cases are observed. For example, when unrestricted in either direction, the Hadamard walk has position that is nearly uniformly distributed in the range [-t/\sqrt 2, t/\sqrt 2] after t steps, which is in sharp contrast to the classical random walk, which has distance O(\sqrt t) from the origin with high probability. With an absorbing boundary immediately to the left of the starting position, the probability that the walk exits to the left is 2/&pgr , and with an additional absorbing boundary at location n , the probability that the walk exits to the left actually increases, approaching 1/\sqrt 2 in the limit. In the classical case both values are 1.

Details

FOCS Conference 1985 Conference Paper

Factoring with Cyclotomic Polynomials

  • Eric Bach 0001
  • Jeffrey O. Shallit

This paper discusses some new integer factoring methods involving cyclotomic polynomials. There are several polynomials f(X) known to have the following property: given a multiple of f(p), we can quickly split any composite number that has p as a prime divisor. For example -- taking f(X) to be X- 1 -- a multiple of p - 1 will suffice to easily factor any multiple of p, using an algorithm of Pollard. Other methods (due to Guy, Williams, and Judd) make use of X + 1, X2 + 1, and X2 ± X + 1. We show that one may take f to be Φk, the k-th cyclotomic polynomial. In constrast to the ad hoc methods used previously, we give a universal construction based on algebraic number theory that subsumes all the above results. Assuming generalized Riemann hypotheses, the expected time to factor N (given a multiple E of Φk(p)) is bounded by a polynomial in k, logE, and logN.

Details
v2026.09.13