Questions

N.B. These questions are provided to give you something concrete to think about to exercise your understanding of the concepts introduced in lectures. Which of them you work is your choice, as is collaboration.

June 18

• Design a Turing Machine, a circuit, and a 1D CA for deciding whether a binary input string has more 1s or more 0s. Define input and output representations; make them as similar as possible.  Compare your solutions in terms of speed, space, and program specification size, as a function of the length of the input string.
• Do the same for adding two binary numbers. 
• Do the same for computing the Nth Fibinacci number, given N.
• In an asynchronous cellular automaton, at each moment a single site (or pair of sites for a BCA) is chosen at random and updated.  Design an asynchronous CA that sorts lists of digits.
• Develop a PLA design (2-level logic) to implement
  • 3b add
  • FSM (simple: stop-light controller; more advanced: for the stop-light at the corner of Chester and Del Mar intended to keep traffic flowing along Del Mar as much as possible, but provide timely breaks when people or cars need to cross (or enter) from Chester. Note the "push-for-walk" buttons and vehicle sensors in the road which will serve as inputs.)
• Develop a 4-LUT FPGA implementation of above
• Consider how each implementation scales (larger addition, more complicated FSM)

June 19

• Estimate the area of the smallest, ``general purpose'' PLA to implement your adder and state machine from the previous day. A design which supports those, but is generalized enough to support a large range of designs?
• Repeat the exercise above for a "general purpose" architecture based on interconnected 4-LUTs.
• Based on (i) high-performance device parameters, (ii) logic transistor count, (iii) clock frequency, (iv) interconnect layer count, (v) an assumed 100% routing track occupancy, and (vi) an assumed 10% ``switching factor'' for logic devices, derive a projection for total power dissipation for the ``high-performance MPU'' through the end of the 2001 ITRS. (Don't forget leakage!) Make sure to explain any additional assumptions needed.

June 20

• Show how to compile a TM into a CA. 
• Show how to compile a BCA into a CA, and visa versa.
• Sketch how an N-bit circuit can be compiled into an initial configuration for the following 2D BCA, where input and output are provided and read out, respectively, from chosen sites in the BCA. (adapted from Margolus, p 136)
• it has four states: { . , o, *, G } meaning {empty, wire, signal, gate}.
• 2 x 2 blocks remain unchanged, unless the set of states in the block is exactly
• o and *: diagonal cells exchange contents
• ., o, and *: in each cell o becomes * and * becomes o
• G and anything: * becomes o in all cells, and in a cell diagonal from a G, o becomes * if there is no other * present.
(Hint: construct wires, show they can cross, construct a NOT gate and a NOR gate.)
• Can the above BCA simulate a Turing Machine, if a finite input region is specified?  How about for a finite input region within a periodic patterned background? 
• Estimate area bounds for a 1024 node network:
  • supporting completely random interconnect
  • Tree or Mesh supporting c=4, p=0.67 designs

June 21

• Show that 2-SAT is in P.  
• Consider the Garden-of-Eden problem: Given a 2D CA rule and a finite configuration (say, bordered by zeros) and a time t, is there any other configuration which leads to the given one in exactly t steps (i.e., can it have a history)? Is this problem in NP?  Is it NP-complete? And if the problem were restricted to t=1?
• Suppose we defined the classes P and NP not in terms of polynomial time computation by a Turing Machine, but rather in terms of polynomial time computation by a Stack Machine, a CA, or a BCA. Would the classes consist of exactly the same problems?
• Invent or suggest a Turing-universal machine model (other than quantum computers) for which the classes P and NP differ from their usual definition in terms of Turing Machines. 
• Consider a ubiquitous technology like a car stereo (may focus on AM/FM radio to be concrete) and/or telephone service.
• What is the ``Architecture'' present to the user?
• Over the past 70 years, how has the implication changed while perserving the same user-visible ``architecture''?
• What is the fault abstraction for some common task? (e.g. calling a friend, but feel free to be creative and pick a different task) What might be a cleaner abstraction? and how might it be supported?

June 24

• Dr. Margolus will be demonstrating the CAM-8 and will help people explore cellular phenomena with it.

July 10

• Given a function f which takes as input an n bit string x and outputs a single bit f(x). This function is guaranteed to be of one of two forms, balanced or constant. A balanced function evaluates to f(x)=1 on half of the inputs x and to f(x)=0 on the other half of the inputs x. A constant function has f(x)=1 for all inputs x or f(x)=0 for all inputs x. Suppose you have a black box which queries this function: you give an input y and the black box gives you f(y). Your goal is to design procedures for determining whether the black box f(x) is balanced or constant using a minimal number of queries to the black box.
  1. If we insist that your algorithm is always correct in determining whether the function is constant or balanced, what is the worst case number of queries the best algorithm will need?
  2. If you allow your algorithm to fail with a small proability, what bounds can you put on the failure probability as a function of the number of queries to the black box.
• Given a function f which takes as input an n bit string x and outputs an n bit string f(x). Again we are given a promise, that f(x) is distinct or distinct on an XOR mask. A function f(x) is distinct if f(x) does not equal f(y) for any distinct x and y. A fucntion f(x) is distinct on an XOR mask if f(x) equals f(x+s) but f(x) does not equal f(y) for all y not equal to x or x+s. Here x+s is the bitwise exclusive OR of the bitstrings x and s. Again we are given access to a black box where we can input x and get as output f(x). We wish to determine whether f(x) is distinct or distinct on an XOR mask in as few queries to the black box as possible.
  1. If we insist that your algorithm is always correct in determing whether f(x) has an XOR mask or not, what is the worst case number of queries the best algorithm will need?
  2. If we allow the algorithm to fail, what bound can you put on the failure rate as a function of the number of queries to the black box?

July 11

• Search for multiple items. Suppose we modify Grover's Search Problem so that the input has exact sqrt(N) ones. Show how to find the index for (any) one of them using O(N^1/4) queries.
• Finding the minimum. Show how to use Grover's algorithm to nd the minimum of N numbers using O(sqrt(N)) comparisons. Prove that this is optimal (Only comparisons are allowed).
• Element Distinctness. The Element Distinctness problem is to decide whether or not the given N numbers are all distinct. Let us assume the only way to access the inputs are by binary comparisons (that outputs =,<=, or >=). It is known that the best classical algorithm needs to compare Theta(N log(N)) times to solve ED. Show how to use Grover's algorithm solve ED using O(N) comparisons. Prove a lower bound of Omega(sqrt(N)) comparisons.
• Can you improve the above (either the lower bound or the upper bound)?

July 12

• 

  Hint: Apply the hybrid argument that we used to show a lower bound for the search problem.

• Show that a quantum error correcting code that is resilient against both a bit- and a phase-flip on one qubit is also resilient against any linear error on one qubit. Verify this for the 9-qubit Shor code.

  What about linear errors on more qubits?

  Hint: Can you express any linear operation on one qubit in terms of the identity (no error), a bit-flip, a phase-flip, and a simultaneous bit and phase flip?

•