Problem Set 7: Quantum
Computing
The Quist for Shor |
Out: 24 March 2003
Due: 4 April 2003, before class |
Collaboration Policy - Read Carefully
For this problem set, you may either work alone and turn in a problem
set with just your name on it, or work with one other student in the
class of your choice. If you work with a partner, you and your
partner should turn in one assignment with both of your names on it.
Regardless of whether you work alone or with a partner, you
are encouraged to discuss this assignment with other students in the
class and ask and provide help in useful ways. You may consult any
outside resources you wish including books, papers, web sites and
people (except for last year's CS200 problem set). If you use
resources other than the class materials, indicate what you used along
with your answer.
Purpose
- Learn about metacircular evaluators
- Understand deeply how a Scheme evaluator works
- Extend an evaluator to define a new language
- Learn about quantum computing
- Solve the Cracker Barrel Peg Board puzzle
Download: Download ps7.zip
to your machine and unzip it into your home directory
J:\cs200\ps7. This file contains:
- ps7.ss — A template for your
answers. You should do the problem set by editing this file.
- meval.ss — a metacircular evaluator for Mini-Scheme.
- listprocs.ss — useful
list procedures (similar to PS6)
- pegboard.ss —
Mini-Scheme code for solving the peg board puzzle
|
A Mini-Scheme Evaluator
In Problem Sets 1-4 we solved problems by dividing them into procedures;
in Problem Set 5, we solved a problem by dividing it into procedures and
state; in Problem Set 6, we solved a problem by dividing it into objects.
In this Problem Set, we will explore how languages can be used
to solve problems. If the languages we have are not well suited
to the problem, we can invent a new language, build an evaluator
for that language, and solve the problem by defining procedures
using the new language.
| Reading: Before going further, you should
have finished reading Structure and Interpretation of Computer
Programs, Chapter 4 (you may skip 4.1.6 and 4.1.7 and 4.4-end).
You should see many similarities between the Scheme variation explained
in Section 4.3, and what you need to do for this problem
set. You can, of course, adapt any code from the text for your solutions. |
The evaluator in meval.ss
defines a Scheme-like language we will call Mini-Scheme. The
language it defines is described by this BNF grammar:
Expression ::= Compound-Expression
Expression ::= Lambda-Expression
Expression ::= Define-Expression
Expression ::= Self-Evaluating
Expression ::= Name
Compound-Expression ::= (Expression Expressions)
Lambda-Expression ::= (lambda
(Names) Expressions)
Define-Expression ::= (define
Name Expression)
Expressions ::= Expression Expressions
Expressions ::=
Names ::= Name Names
Names ::=
Self-Evaluating ::= Number
Self-Evaluating ::= Primitive-Procedure
Self-Evaluating ::= String
The language is defined by its evaluation procedure,
meval, that takes an expression and an environment and
evaluates the expression in the passed environment.
Below
are some sample interactions using meval. We use '
(quote) to prevent the underlying Scheme interpreter from attempting to
evaluate the Mini-Scheme expression we pass to meval.
> (meval '3 the-global-environment)
3
> (meval '(+ 3 3) the-global-environment)
6
> (meval '(+ 3 3) the-empty-environment)
No binding for +
> (meval '(define x 3) the-global-environment)
ok
> (meval 'x the-global-environment)
3
> (meval '(define square (lambda
(x) (* x x)))
the-global-environment)
ok
> (meval '(square x) the-global-environment)
9
> the-global-environment
#1=(((+ primitive-procedure #)
(* primitive-procedure #)
(- primitive-procedure #)
(x . 3)
(square procedure (x) ((* x x)) #1#)))
In meval.ss, we have provided a procedure (driver-loop)
that runs a read-eval-print loop for Mini-Scheme. Try running (driver-loop)
and evaluating some Mini-Scheme expressions. For example:
> (driver-loop)
;;; Mini-Scheme input:
(define square (lambda (x) (* x x)))
;;; Mini-Scheme value:
ok
;;; Mini-Scheme input:
(square (square 3))
;;; Mini-Scheme value:
81
;;; Mini-Scheme input:
quit
Done.
Play around with Mini-Scheme a little to get a feel for how it works,
and what is different from the DrScheme interpreter.
Extending Mini-Scheme
Our Mini-Scheme language is missing some important things. For example,
it does not provide if.
Eva Lu Ator claims she can define if herself using Mini-Scheme:
(meval '(define true (lambda (x y) x)) the-global-environment)
(meval '(define false (lambda (x y) y)) the-global-environment)
(meval '(define if (lambda (pred tbranch fbranch)
(pred tbranch fbranch)))
the-global-environment)
And demonstrates her definitions as follows:
(meval '(if true 3 5) the-global-environment)
3
(meval '(if false (+ 3 5) (+ 7 12)) the-global-environment)
19
Question 1:
Convince Eva Lu
Ator that her if is inadequate by showing an expression
which it would not evaluate correctly. Explain why it is impossible
to define a procedure in Mini-Scheme that behaves like the Scheme
if (that is, why if must be a special
form).
|
Question 2:
Extend the provided Mini-Scheme implementation to support
the special form if, that does the same thing that Scheme's
if special form does. You will need to add a new evaluation
rule to the meval procedure. |
The Mini-Scheme global environment defines true and
false (as the underlying #t and #f constants,
not as Eva defined them). After adding the special form if you should
get these interactions:
> (driver-loop)
;;; Mini-Scheme input:
(if true 3 5)
;;; Mini-Scheme value:
3
;;; Mini-Scheme input:
(if false (+ + +) (+ 7 12))
;;; Mini-Scheme value:
19
You should also be able to solve the peg board puzzle.
Note that Mini-Scheme is much slower than standard Scheme, so it will take a
really long time to solve the 5 row pegboard puzzle. Try solving the
4-row puzzle instead. (We show the result for the 5-row puzzle
as well, in case you need it next time you go to Cracker
Barrel, but you are discourage from waiting for it to evaluate yourself):
> (load "pegboard.ss")
> (driver-loop)
;;; Mini-Scheme input:
(solve-pegboard (make-starting-board 4 (make-position 2 1)))
;;; Mini-Scheme value:
(((4 1) (3 1) (2 1)) ((1 1) (2 1) (3 1)) ((3 3) (2 2) (1 1)) ((3 1) (3
2) (3 3)) ((4 4) (3 3) (2 2)) ((1 1) (2 2) (3 3)) ((4 2) (4 3)
(4 4)) ((4 4) (3 3) (2 2)))
;;; Mini-Scheme input:
(solve-pegboard (make-starting-board 5 (make-position 2 1)))
;;; Mini-Scheme value:
(((4 1) (3 1) (2 1)) ((1 1) (2 1) (3 1)) ((4 3) (3 2) (2 1)) ((5 2) (4
2) (3 2)) ((2 2) (3 2) (4 2)) ((4 4) (3 3) (2 2)) ((5 4) (5 3)
(5 2)) ((5 1) (5 2) (5 3)) ((2 1) (3 1) (4 1)) ((4 1) (4 2) (4
3)) ((5 3) (4 3) (3 3)) ((2 2) (3 3) (4 4)) ((5 5) (4 4) (3 3)))
Quantum Computing
Normal computers are based on classical mechanics — computation is done
using electricty and magnetism, more or less as understood since Maxwell
(1873). Quantum computers are based on quantum mechanics, laws
of physics that apply at the lowest levels of matter. GEB Chapter 5 (p.
142-146) discussed quantum mechanics. At the lowest level, particles are
actually in several states at once. Quantum particles have the very strange
property of being in more than one state at the same time.
In the eary 1980s, Richard Feynman and others suggested that this property
may be useful for performing computations. The first important algorithm
for a quantum computer was invented by Peter Shor in 1994 (Polynomial-time
algorithms for prime factorization and discrete logarithms on a quantum
computer, SIAM Journal of Computing). He demonstrated that if
you had a quantum computer you could take advantage of the multiple states
property to solve the problem of factoring large numbers. With normal
computers, there is no known polynomial time solution to factoring. With
Shor's quantum algorithm, it is possible to factor in polynomial time
with a quantum computer. Factoring is a very important problem since many
cryptosystems depend on factoring being hard for their security. (You
can think of the box in the movie Sneakers as a quantum computer
that can factor quickly.)
When Shor published his paper no one had yet built a quantum computer
(at least as far as the general public knows — the National Security Agency
does lots of secret work in quantum computing, but doesn't tell many people
about it!). Recently, people have built real quantum computers. IBM recently
used Shor's algorithm on a quantum computer to factor 15 (into 3 x 5).
(Big Blue
Takes Quantum Step, Wired, December 2001)
The smallest unit of quantum information is known as a qubit.
A standard bit is the smallest unit of information in a normal computer.
A bit can be in one of two states — 0 or 1. A qubit,
however, is a superposition of many states at the same time. In other words, a qubit can
represent both 0 and 1 at the same time. With two normal
bits, we can represent four different values. We can think of two qubits
as representing four different values at once. The quantum computer that
factored 15 had 7-qubits, enough to be in 27 (= 128) states
at once. If we could build a thousand qubit quantum computer, we could
use it to quickly factor large numbers. Making an extra qubit, though,
is extremely hard. Most physicists believe it is practically impossible
to build a many-qubit quantum computer. There may be potential side effects
to the surrounding area with a quantum computer that has more than 10
or 12 qubits. See http://www.qubit.org/intros/comp/comp.html
for more information on quantum computing (but it is not necessary to
understand quantum physics to do this problem set).
For this problem set, you will be extending our Mini-Scheme evaluator
to support a model of computation inspired by quantum computing. We'll
call the new language Quini-Scheme. Although Quini-Scheme is
inspired by quantum computing, we have made some very
unreasonable assumptions about future quantum computers to make
it simpler to program. No conceivable quantum computer
actually works this way.
To model quantum computers, we will extend our Mini-Scheme evaluator
with quists, short for quantum lists. A quist is a list of values,
but unlike a normal list it represents all of the values at the same time.
For example, (quist 0 1) would represent a single qubit, storing
both 0 and 1 at the same time. To represent (quist 0 1 2 3) we
would need two qubits since it represents four possible values.
Expressions involving quists evaluate to a quist of the value of the
expression for all possible values in each of the quists.
The order of the values in a quist does not matter. For example, (quist
3 4) means exactly the same thing as (quist 4 3).
Further, it does not matter how many times the same value
appears in a quist. We consider (quist 0 1 1 2 2 2 2) to
mean the same thing as (quist 2 1 0). A quist cannot
be nested within another quist — that is the possible
values of a quist cannot contain other quists.
Make sure you understand these examples before continuing:
;;; Quini-Scheme input:
(quist (+ 1 2) 4)
;;; Quini-Scheme value:
(quist 3 4)
;;; Quini-Scheme input:
(quist (list 0 1) (list))
;;; Quini-Scheme value:
(quist (0 1) ())
;;; Quini-Scheme input:
(- (quist 7 8 9))
;;; Quini-Scheme value:
(quist -7 -8 -9)
;;; Quini-Scheme input:
(define square (lambda (x) (* x x)))
;;; Quini-Scheme value:
ok
;;; Quini-Scheme input:
(square (quist 1 2 3))
;;; Quini-Scheme value:
(quist 1 4 9)
;;; Quini-Scheme input:
((quist + -) 6)
;;; Quini-Scheme value:
(quist 6 -6)
;;; Quini-Scheme input:
((quist + -) (quist 9 10))
;;; Quini-Scheme value:
(quist 9 10 -9 -10)
For simplicity, we will change the application expression in
Quini-Scheme to only allow applications with a single parameter. That
is, we replace the rule:
Compound-Expression ::=
(Expression
Expressions)
with a simpler rule:
Compound-Expression ::=
(Expression
Expression)
The next 4 questions will extend your Mini-Scheme evaluator to support
quists. Once you have finished them, all the examples above
should work with your Quini-Scheme evaluator.
Question 3:
Implement eval-quist so that your Mini-Scheme evaluator
correctly evaluates anything of the form (quist <elements>)
that we have defined as legal. Assume that your evaluator knows
how to evaluate any member of the quist. To test your implementation,
try evaluating (quist (+ 1 2) 4) and (quist (list 0
1) (list)). You should get the same results as the
examples above.
|
Question 4:
Modify apply-primitive so that your Mini-Scheme evaluator
correctly evaluates anything of the form (<primitive-procedure>
<quist>). You may find it useful to define and use a
procedure called apply-primitive-to-quist-contents. To
test your code, try evaluating (- (quist 7 8 9)). Also,
make sure make sure your evaluator still correctly evaluates regular
applications of primitive procedures, including those with no operands,
like (list).
|
Question 5:
Modify apply-compound so that your Mini-Scheme evaluator
correctly evaluates anything of the form (<compound-procedure>
<quist>). You may find it useful to define and use a
procedure called apply-compound-to-quist-contents. To test
your code, try evaluating (square (quist 1 2 3)). Also
make sure your evaluator still correctly evaluates regular applications
of compound procedures, including those with no operands, like (square-two),
where square-two is defined: (define square-two (lambda
() (* 2 2))).
|
Question 6:
Implement apply-quist so that your Mini-Scheme evaluator
correctly evaluates an application of the form ((quist <procedures>)
<operand>). To test your implementation, try evaluating
((quist + -) 6) and ((quist + -) (quist 9
10)).
|
Observing Quists
To do useful computations with quists we need to convert them back into
normal values. Potentially (again, this may not actually be possible in
our universe), one can observe a quantum particle, which would force it
into one of its possible states, at which point we could examine some of
its properties. We will model this using an observe special form
that takes a quist and a procedure and produces a normal value. In
actual quantum computers, turning quantum information into normal
values is much harder.
The observe form takes a function that evaluates to a boolean
when it is applied to a value of any type and a quist. The value of an observe
is the first value in the quist for which the function evaluates to true, if there
is one. A more realistic quantum computing
model would randomly pick one of the values in the quist for which
the test procedure evaluates to true, but for simplicity it is
fine if your observe always evaluates to the first value
that satisfies the test procedure. If there is no such value, it should return an error stating that
the quist is unobservable.
(On the real quantum computer, an unobservable
quist might lead to a chain-reaction explosion that engulfs the universe.
For the purposes of this assignment, it is not necessary for your simulator
to produce the same effect; in fact, ITC discourages you from
attempting to produce this effect on the public lab machines.)
Here are some examples:
;;; Quini-Scheme input:
(observe (lambda (x) true) (quist 0 1))
;;; Quini-Scheme value:
0
;;; Quini-Scheme input:
(observe (lambda (x) false) (quist 0 1))
;;; Quini-Scheme value:
Error: unobservable quist.
;;; Quini-Scheme input:
(observe (lambda (x) (> x 10)) (quist 3 17 8 23 -4))
;;; Quini-Scheme value:
17
;;; Quini-Scheme input:
(observe list? (quist 3 (list 0 1) (list) 17 (list 2 3)))
;;; Quini-Scheme value:
(0 1)
Question 7: Explain why observe
must be a special form.
|
| Question 8: Extend your implementation to
support observe. Try out your evaluator on the
examples above.
|
The Quantum Peg Board Puzzle
Note: Good answers to questions 1-8 are enough to get a Gold Star
on this assignment. Question 9 is available for those of you who are not
satisfied with a single Gold Star (or don't have any other classes this
semester) and are seeking a real challenge.
In pegboard.ss we have provided a
Mini-Scheme solution to the peg board puzzle. It tests all possible
sequences of moves until it finds a solution (a sequence of moves that
leaves just one page), or has tried every possible sequence without
finding a winning solution.
| Question 9: Modify our peg board code to take
advantage your Quini-Scheme special forms. Although it won't help the
program run faster since we only have classical computers to run
it on, your code should make it possible to solve the peg board
puzzle in polynomial time if we had a computer that could
evaluate expressions involving arbitrarily large quists in the
same amount of time it takes to evaluate those expressions for a
normal value.
|
Credits: This problem set was revised for CS200
Spring 2003 by Jacques Fournier and David Evans. The original problem set was
created for CS200 Spring 2002 by Stephen Liang and David Evans,
based on a problem
set created for CS655 Spring 2001.
