| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | September 14, 2007 |
| Latest Amendment Date: | September 14, 2007 |
| Award Number: | 0729172 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Dmitri Maslov
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 15, 2007 |
| End Date: | August 31, 2009 (Estimated) |
| Total Intended Award Amount: | $69,230.00 |
| Total Awarded Amount to Date: | $69,230.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
3227 CHEADLE HALL SANTA BARBARA CA US 93106-0001 (805)893-4188 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
3227 CHEADLE HALL SANTA BARBARA CA US 93106-0001 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | THEORETICAL FOUNDATIONS (TF) |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
"Quantum Algorithms for Data Stream"
Wim van Dam, University of California, Santa Barbara
In this project the investigator develops new algorithms for processing data streams that are much larger than the internal memory of the quantum computer that executes the quantum algorithm. Such algorithms are especially relevant in an "online" setting where the computer deals with a continuous and unpredictable flow of information that has to be processed in real time without the possibility of storing the information for further analysis. The research of this project focuses on the question how much better (future) quantum mechanical computers will be at performing such tasks in comparison with our current, classical computers.
While N quantum bits can carry no more than N bits of classical information, there is ample evidence from earlier work on quantum finite automata and quantum communication that for specific tasks the required amount of quantum bits can be significantly lower than the required number of classical bits. Here it is investigated if these kinds of quantum improvements can also be obtained in the data stream model. The research applies ideas from the theory of quantum computation to the new setting of data stream algorithms, which gives a computational model that sits at the intersection of the theories of quantum finite automata and quantum communication complexity. As quantum devices in the near future will most likely have a very limited amount of memory, this data stream model is arguably more realistic, from an experimental point of view at least, than the general quantum circuit model with its more generous assumptions regarding the availability of memory.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
Please report errors in award information by writing to: awardsearch@nsf.gov.
