Lecture 16 Quantum computing Ubiquitous Internet Services The client server paradigm DNS Electronic Mail World Wide Web 1 Quantum Computing In a quantum system the amount of parallelism increases exponentially with the size of the system. Access to the results disturbs the quantum state through a process called decoherence. Qubit a unit vector in a 2-dimensional complex space where a complex base has been chosen. 2 Classical mechanics The individual states of particles combine through the cartesian product.
If X and Y are vectors the vector product has dimension dim(X) + dim(Y). Given a system of n particles the states of the system form a vector space with 2 x n dimensions. Given n bits we can construct 2n n-tuples and describe a system with 2n states. 3 Quantum mechanics The individual states of particles combine through the tensor product. If X and Y are vectors the vector product has dimension dim(X) x dim(Y). Given a system of n particles the states of the system form a vector space with 2n dimensions. The extra states that do not have a classical analogy are called entangled states. 4 Quantum mechanics (condt) A quantum bit can be in infinitely many superposition states. When the qubit is measured the measurement changes the state of the
particle to one of the two basic states, thus from a qubit we can only extract a clasical bit of information. Example the use of polarized light to transmit information. 5 | > a | b E > (a) E A S
S intensity = I intensity = I/2 (b) (c) E B A S A C E B S
intensity = 0 (d) intensity = I/8 (e) 6 Polarized light A photons polarized state can be modeled as a unit vector and expresses as a combination of two basis vectors. There are infinitely many possible orientations of the unit vector a qubit can be in infinitely many superposition states. Measuring the polarization is equivalent with projecting the random vector onto one of the two bases. 7 Quantum algorithms 1994 Peter Shor found a polynomial time algorithm for factoring n-bit numbers on quantum computers.
The algorithm reduces the factoring problem to finding the period of a function and uses quantum parallelism to find the superposition of all values of the function in one step. Then the algorithm calculates the quantum Fourier transform of the function in one step. 8 Ubiquitous Internet Services The client-server paradigm. Asynchrounous RPCs Servers are reactive programs. Stateless versus statefull servers. 9 time t1 Client Thread
Server Thread Request t2 t3 t4 Response 10 DNS DNS Domain Name System, RFC 1034-5 Distributed database consisting of a hierarchy of name servers. Each organization has one or more local or authoritative name servers. Maps host names to IP addresses. 11 Client Request
Response host name host name host name domain name IP address DNS Server Canonical Host Name Host name of Mail server Host name of a server who knows how to map addresses in that domain 12 DNS records Local Name Server/ Authoritative Name Server (3,4) DNS records Root Name Server
(2,3) (7,8) Local domain (7,8) (4,5) Web Server (7,8) (2,3,4,5) (7,8) (1,6) Web Browser on Local PC Local domain (1,2,3,4,5,6) DNS records Local Name Server
13 Electronic Mail Asynchronous communication model SMTP based upon TCP. 14 Sender's Mail Agent Shared Email Server Shared Email Server Receiver's Mail Agent Sender's outbox Sender's
outbox Receiver's inbox Receiver's inbox SMTP SMTP POP/IMAP 15 The World Wide Web Developed at CERN in late 80s. Stateless servers. URLs identify a host and the path to a resource (file) on that host. HTTP Hypertext Transfer Protocol HTML Hypertext Markup Language 16
An HTTP request contains one of the following methods: GET - get a resource HEAD - verify the link and conditions of a resource POST - input to a resource, usually a CGI script PUT - store a resource at the server DELETE - delete a resource TRACE - include all headers in a response Client HTTP request Web Browser TCP port HTTP response Persistent/ NonPersistent HTTP connection
Web Server HTTP request Web Cache HTTP response Thread handling an HTTP request TCP port Thread handling an HTTP request Client Local cache TCP port
Sample HTTP status code in a response 100 - Continue 200 - OK 205 - Reset Connection 301 - Moved Permanently 304 - Not Modified 402 - Payment Requried 404 - Not Found 405 - Method Not Allowed 407 - Proxy Authentication Required 415 - Unsupported Media Type 500 - Internal Server Error 504 - Gateway Timeout 505 - HTTP version Not Supported Resource Repository 17 Browser User's HTTP request Web Server SYN
RTT SYN TCP connection establishment ACK Response time HTTP request ACK Server residence time. Web page is created on the fly Data User's HTTP request for an image ACK HTTP request ACK Server residence time. Image is retrived from
disk Response time Data 18 Request Line Method Name URL of Object Header Lines Header Field Name Browser Version Field Value Response Line Method Status
Name Code Header Lines Header Field Name Phrase Field Field Value Value Body Body GET /example/index.html HTTP/1.1 Host: www.bond.com User-Agent: Mozila/4.0 Accept: text/html, image/jpeg Accept-Encoding: gzip From: [email protected] HTTP/1.1 200 OK Connection: close Date: Sat, 29 Jan 2000, 10:15:04 GMT Server: Apache/1.3.0 (NT)
Last-Modified: Thu, 27 Jan 2000, 09:31:56 MT Content-Length: 12266 Content-Type: text/html DATA 19 HTTP server cache HTTP request Web browser cache HTTP response Public/shared Web cache HTTP request HTTP response HTTP server
cache HTTP request Web browser cache HTTP response HTTP server cache HTTP server cache 20 Back End Data request Client Data
request request response response response Front End (a) Data Back End response request Data response Front End request Client
request request Router response Data Data Data Network File System response Data (b) 21 Company user Internet Firewall
Private network Web Server (a) External user Firewall External client Proxy External HTTP/TCP connection Web Server Internal HTTP/TCP connection (b) 22
