2000 — 2006 |
Kimble, H. Kitaev, Alexei (co-PI) [⬀] Preskill, John [⬀] Schulman, Leonard Scherer, Axel (co-PI) [⬀] Doyle, John (co-PI) [⬀] |
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information |
Itr: Institute For Quantum Information @ California Institute of Technology
EIA -0086038 Kimble, H.J. California Institute of Technology
Title: Information Technology Research: Institute for Quantum Information
An interdisciplinary team of researchers in Physics, Applied Physics, Electrical Engineering and Computer Science are establishing an Institute for Quantum Information (IQI) to facilitate the investigation of quantum information science to provide new capabilities in the revolutionary field of quantum computing. To this end, efforts are being made to develop new algorithms for the manipulation, processing, and distribution of quantum information (including information capacities of communication channels, reliable schemes for distributed computation, efficient quantum error correcting codes). Investigations of physical systems for the implementation of quantum computation and communication, as well as coherent nanotechnology, principally by the way of theoretical models and analysis, are being performed. The team is also pursuing techniques to develop active control of quantum effects in nanoscale integrated circuits involving systematic approaches to the suppression of unwanted quantum effects via on-chip feedback networks and methods for stabilizing and exploiting emergent quantum behaviors in the context of analog/hybrid VLSI.
|
0.915 |
2003 — 2008 |
Schulman, Leonard Murray, Richard [⬀] Effros, Michelle (co-PI) [⬀] Low, Steven (co-PI) [⬀] Hassibi, Babak (co-PI) [⬀] |
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information |
Itr: Information Dynamics For Networked Feedback Systems @ California Institute of Technology
This project is developing a new framework for investigating the dynamics of information in complex, interconnected systems. The key technical thrusts of the project are: (1) real-time information theory, (2) robust control of networks, (3) packet-based control theory,and (4) computational complexity of network systems. Each of these thrusts explores aspects of information systems that must interact with the real-world in a manner that requires careful control of the timing of the computation and the evolution of the information state of the system. While diverse in application, these thrusts represent a common core of intellectual thrusts that integrate computer science, control, and communications.
The results of the proposed research are being evaluated on two testbeds already at Caltech. The first is the Multi-Vehicle Wireless Testbed, which provides a distributed environment for control of 8-10 vehicles performing cooperative tasks in a real-time environment. The second is the WAN in Lab, a wide area network consisting of high speed servers, programmable routers, electronic crossconnects, and long haul fibers with associated optical amplifiers, dispersion compensation modules and optical multiplexers.
The project is also developing elements of a curriculum that will provide training to students in information systems that blends communications, computation, and control. This includes integration our the research framework into a recently created course at Caltech on the principles of feedback and control, CDS 101, as well as development a second course, IST 201, aimed at bringing together faculty and students interested in working on problems at the boundaries of these traditional disciplines.
|
0.915 |
2005 — 2009 |
Schulman, Leonard |
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information |
Algorithms For Data Analysis @ California Institute of Technology
Intellectual merit of the proposed activity. The primary focus of this investigation is the following ubiquitous algorithmic challenge: Given a large data set, provide a "simple" yet "accurate" description of the data.
The question is treated at several levels. In the first it is considered as a data-clustering problem. A clustering algorithm (designed with regard to a particular "distortion" that measures dissimilarity of points) partitions the data into clusters so that the distortion between points within a cluster is minimized (i.e., similarity is maximized), while the distortion across clusters is maximized. In the huge databases prevalent in scientific, engineering, business, government and medical applications, "polynomial time algorithms" are not good enough since a typical algorithm running in quadratic or cubic time is too slow to be executed on gigabytes or terabytes of data. This proposal therefore places an emphasis on near-linear time algorithms. A particular novel approach, recently developed by the proposer, is described.
In the second treatment, more advanced data analysis problems are addressed. In these problems richer and more flexible models for the data are allowed, such as mixture models of several low-degree surfaces. Data analysis in these models is beyond the reach of current approximation algorithms. The data analysis requires partitioning of the data, and so the NP-completeness of clustering is inherited; but in addition, new difficulties are inherited from applied statistics, such as the issue of missing or incomplete records in real world data. The combination requires solution of fundamental new algorithmic and geometric questions.
The third part of the proposal is concerned not with a particular clustering problem but with setting up the right kind of theory for such nonparametric inference problems. The fundamental principle is this: We should seek to cluster only data sets that admit a high-quality clustering. Often, what makes a particular input hard for a clustering algorithm is that its best clustering is little better than average: the input does not separate cleanly into well-separated pieces. A good data analysis should detect this fact, rather than stall on a search for a best yet near-average clustering. Developing a sound theoretical framework for clustering therefore requires departing from the "worst-case analysis" framework that has been dominant so far.
The fourth part of the proposal is devoted to theoretical analysis of the EM clustering algorithm and its variants. EM is an iterative heuristic for which there are few performance guarantees. However, it is fast, and widely used in practice. Because of this, an important goal is to determine under what conditions EM performs well, and what conditions require other approaches.
The fifth part of the proposal is devoted to a different topic: the limitations imposed on feedback Control mechanisms because of limited processing power or limited communication capacity. Because of the real-time nature of control tasks, conventional "input-output" circuit complexity is not an appropriate theoretical framework. Two general types of questions are pursued. The first is characterization of the class of stabilization tasks that can be performed by highly parallelized, ultra-fast digital control circuits. The second is the ensuring of reliable and real-time communications among components of a control system in spite of noise on the communication channels.
Broader impact of the proposed activity. Data analysis is required in many scientific, engineering, business, government and medical applications. The importance of sifting out useful information from huge databases is such, that advances in data analysis algorithms as well as in the mathematical framework underpinning the design of these algorithms, has significant potential benefit to society.
Increasing automation in our technological infrastructure has created a convergence of control, computation and communication technologies. Some of the difficulties associated with carrying out this convergence will be resolved through progress on the questions described in the last section of the proposal.
All topics in the proposal are highly suited to graduate, and in some cases undergraduate, research. Interdisciplinary student training in algorithms, complexity, control and information theory is ongoing (by the PI and several colleagues). Increase in this activity is intended during the period of the proposed investigation.
|
0.915 |
2005 — 2014 |
Kimble, H. Kitaev, Alexei (co-PI) [⬀] Preskill, John [⬀] Schulman, Leonard Refael, Gil (co-PI) [⬀] |
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information |
Institute For Quantum Information @ California Institute of Technology
Quantum information science (QIS) is devoted to understanding how the fundamental laws of quantum physics might be harnessed to dramatically improve the acquisition, transmission, and processing of information. The potential scientific and technological payoff from QIS is vast, but many deep and fundamental problems must be solved before that potential can be fulfilled. These advances will require contributions from scientists trained in a variety of subjects who are bold enough to disregard the traditional boundaries between disciplines and to pool their efforts in building an important new field. With this need in mind, the Institute for Quantum Information (IQI) was founded at Caltech in September 2000, supported by a five-year $5M Information Technology Research (ITR) award from NSF. Since September 2005, the IQI has been supported by a three-year award sponsored jointly by the Physics at the Information Frontier program (PIF) in MPS/PHY, the Emerging Models and Technologies for Computation Cluster (EMT) in CISE/CCF, and the Office of Multidisciplinary Activities (OMA). The IQI, led by a multidisciplinary team of five Caltech professors, is devoted to building the theoretical foundations of quantum information science across a broad front encompassing quantum algorithms, quantum cryptography, quantum information theory, fault-tolerant quantum information processiThe research accomplishments of the IQI have clear intellectual merit. Since September 2000, IQI participants have produced 282 publications covering all aspects of theoretical QIS; of these 86 were generated since the onset of our current award in September 2005. Some noteworthy achievements during the past two years are: (1) Progress in quantum algorithms, such as the discovery of an exponential speedup for finding hidden nonlinear structures. (2) Insights into quantum communication, such as a proof of the quantum channel capacity theorem based on decoupling of the environment. (3) Studies of quantum entanglement, such as a characterization of the monogamy of nonlocal correlations. (4) Tools for fault-tolerant quantum computation, such as a scheme for protecting against highly biased noise. (5) Proposals for quantum hardware, such as a protected qubit based on a superconducting current mirror. (6) Connections between quantum information theory and quantum many-body theory, such as new proposals for experiments that probe the non-abelian statistics of quantum Hall quasiparticles. The broader impact of the IQI also has many facets. With the end of scalability of conventional siliconbased information technology on the horizon, it is vitally important to explore aggressively new paradigms for information technology. IQI contributions are broadening the nation's technical base, ensuring US leadership in the future development of quantum science and technology. The IQI has attracted and trained top postdoctoral scholars, 16 of whom have moved on to faculty positions (or the equivalent) elsewhere, thus significantly strengthening the world effort in QIS. The IQI has also trained many Ph.D. students who are still working in the field, and we have sponsored a variety of undergraduate research projects. A particularly important aspect of the IQI?s broader impact is a vibrant visitor program.
Since 2000, we have sponsored 120 visits by senior and postdoctoral scholars, and 70 visits by graduate students from other institutions. The visitor program fuels intellectual excitement,facilitates collaborations and exchanges of scientific ideas, and performs a highly valued service for the international QIS community. The IQI can best ensure its continued success by nurturing its distinctive qualities: a focus on interdisciplinary research, an emphasis on fostering the career development of world-class postdoctoral talent, and devotion to an active visitor program. At the same time, in response to new scientific opportunities, the mission of the IQI will evolve in important ways over the next several years. Two increasingly prominent themes will be the exciting interface of QIS with condensed matter physics, and the daunting challenge of closing the considerable gap between the theory and experimental practice of QIS and physical implementations of quantum computing. Basic advances in all of these areas are needed to bring revolutionary quantum technologies closer to realization.
|
0.915 |
2005 — 2008 |
Schulman, Leonard |
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information |
Qntm: Collaborative Research: Quantum Algorithms @ California Institute of Technology
1. Intellectual Impact Research is proposed on two Areas of Interest in NSF Solicitation 05-501: Development of a broad and general collection of quantum algorithms; Quantum simulation of quantum systems. Specific topics: Hidden subgroup problems: The status of the non-abelian hidden subgroup problem (HSP) is one of the most fundamental open problems in quantum algorithms. In particular, the graph automorphism problem may be formulated as a hidden subgroup problem over the symmetric group S n . The abelian case can be effectively computed with a quantum computer by repetition of coset state preparation and Fourier sampling. The natural generalization of this method to nonabelian groups is commonly referred to as the standard method for the nonabelian HSP. The performance of this algorithm depends upon properties of the irreducible complex representations of the group. However in most cases they do not yet yield useful algorithms. Research is proposed on improving these methods as well as determining in which cases they are bound for failure and other methods are necessitated. Algorithmic cooling: Algorithmic cooling is an inescapable component of quantum algorithms: for example, we can even view fault-tolerant computing as moving heat (random errors) out of the computation registers. These issues are particularly pressing in the context of liquid-state NMR quantum computing as well as ion trap quantum computing, and we have studied them (especially in the NMR context) in the past, obtaining results that are nearly best-possible for closed-system cooling. These results reveal, however, that closed-system cooling cannot be powerful enough to turn warm systems into large-scale quantum computers. We are therefore turning to the study of open-system algorithmic cooling. This requires new algorithmic techniques. Also, since open systems are more sensitive to decoherence than closed systems, more careful modeling of these effects will be required. Fault-tolerant Quantum Comptutation: Decoherence is the major obstacle to the experimen- tal realization of quantum computers. Over the last year there have been two significant break- throughs in the ability to carry out fault-tolerant quantum computation in the presence of deco- herence. The main idea in both cases is the use of uniquely quantum features to limit the exposure of data to decoherence. We plan to explore these ideas further to a) improve the overhead in the number of ancillas discarded and therefore the total number of qubits required b) improve the threshold and decrease computational overhead for more realistic error-models 2. Broader Impact Societal impact: Even if quantum computers are a distant reality, encryption of data today so that it cannot be decrypted at a future time, depends upon the development of cryptosystems resilient to attacks by quantum computers. This in turn demands an understanding of what problems are and are not tractable on quantum computers, a core topic of the proposed research. Educational impact: Ideas from quantum computation and quantum information can poten- tially have a major impact on how basic quantum mechanics is taught (quite apart from teaching quantum computation, which is also part of our efforts). We propose to create course material to make this happen.
|
0.915 |
2007 |
Schulman, Leonard |
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information |
Sger: Planning For a Cross-Cutting Initiative in Computational Discovery @ California Institute of Technology
The initiative must be designed to attract the best researchers from both the Theoretical Computer Science (TCS) community and, crucially, the other scientific and engineering disciplines in which the ideas are to be applied. In preparing a detailed initiative, it is essential to incorporate the advice and cooperation of leading researchers in all these fields. For this purpose it is proposed to hold two two-day planning workshops, with thirty to forty participants in each. About a third of the participants will be invited speakers, a third will be invited discussants, and a third will be selected from the TCS community. The distinguishing feature of these workshops will be their multidisciplinary nature; experts from different areas will be invited and asked to focus on the computational lens and its use in solving problems from their field. The first workshop is tentatively planned for early December, 2006 at Princeton University, and the second for mid-March, 2007 at Caltech. Because of the wideranging nature of the scientific disciplines involved, the first workshop will focus on Biological and Earth Sciences, and the second on Physical and Mathematical Sciences. A report for the NSF based on the workshops will be completed by Summer, 2007.
The intellectual merit of this proposal is the development of viable, promising courses of future interaction between CS and other disciplines. The broader impact will be that upon follow-on research: both directly by participants in the workshops, but ultimately much more widely if the workshops lead to an NSF cross-cutting initiative.
|
0.915 |
2008 — 2011 |
Schulman, Leonard |
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information |
Collaborative Research: Emt/Qis: Quantum Algorithms and Post-Quantum Cryptography @ California Institute of Technology
Collaborative Research: EMT/QIS: Quantum Algorithms and Post-Quantum Cryptography Project Summary
Cryptography is the basic infrastructural element enabling privacy and security for electronic transactions. However, when a large-scale quantum computer is finally built, it will force us to abandon established methods of cryptography, such as RSA and Diffie-Hellman, which are in common use today. The proposed research will further this line of disruptive quantum algorithmic research; but it also aims to erect a new framework of secure post-quantum cryptography, in order to maintain this societally critical infrastructure.
The most attractive approach for salvaging modern cryptography would be to develop classical cryptosystems for which we have compelling evidence of security even in the face of quantum adversaries. Recent work by the PIs and their collaborators has shown that certain algebraic problems possess hardness properties relevant even for quantum algorithms. We propose to strengthen and leverage these results in order to develop cryptographic schemes which can be carried out by today's computers, but which will remain secure even against quantum attack in the future.
In tandem with this effort, we propose to develop new quantum algorithms for breaking cryptosystems based on conjugacy in the braid group. This is one of the few remaining classical cryptosystems which has not already been shown to be vulnerable to quantum attack.
Our research program is also directly integrated with graduate student training at all four institutions, undergraduate educational innovation, educational outreach, and broad scientific dissemination.
|
0.915 |
2011 — 2013 |
Schulman, Leonard |
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information |
Af: Eager: Algorithms in Linear Algebra and Optimization @ California Institute of Technology
Dr. Schulman's research will tackle two problems of central importance in computer science: (1) Linear programming in strongly polynomial time and (2) Matrix pre-conditioning by diagonal balancing. A strongly polynomial-time algorithm for linear programming would be a breakthrough in complexity theory over the real field. It may lead to improved algorithms for harder types of convex programming (e.g., semidefinite) which (albeit in polynomial time) are currently prohibitively slow. Better algorithms for matrix preconditioning have the potentially to significantly improve linear algebra software packages.
|
0.915 |
2013 — 2017 |
Schulman, Leonard |
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information |
Af: Small: Algorithms For Inference @ California Institute of Technology
The first focus of this award is the problem of inferring causal relationships. This problem is essential to many statistical applications. Generally speaking, causation can be inferred only by active intervention, through controlled experiment. However such experiments may be impossible or else practically or morally infeasible: for instance, in predicting potential effects regulations or laws on medical, educational and economic outcomes, or, in predicting whole-ecosystem effects of human activity. The starting point for Dr. Schulman's research in this area is Pearl's theory of Structured Causal Models (SCM) which, allows, in special circumstances, "identification" of a causal relationship (as opposed to a statistical correlation) from passive observation. The proposed research aims, in the first place, to expand the above special class of circumstances---and thereby make the theory more widely applicable---by using a relaxed but still useful notion of "weak identification" of causal relationships. The relaxed notion is more robust, and enables valid inference even if the posited SCM is slightly inaccurate. In the second place, the research aims to provide efficient and numerically stable algorithms for weak identification from empirical data.
The second focus of this award, again in computational statistics, is the representation of a large data set (considered as an empirical measure) by a much smaller data set, in such a way that for a specific family of integrals, all integrals of the measure are approximately preserved. This work encompasses two separate application areas. The first concerns clustering and related high dimensional data analysis problems. Here the compressed data set is known as an epsilon-approximation or core-set of the input measure. A particular focus is on "underclustering", namely, preparation of core-sets for clustering in a normed space, before the norm has been specified. The technical tools needed in this application have to do with recently developed ideas about the "total sensitivity" of the family of integrals, as well as with, on the algorithmic side, bicriteria approximations. The second application area concerns signal processing (or approximation theory) on compact groups. Here the methods draw on representation theory, the classical theory of the moment problem, and convex geometry.
This award will be used to train graduate students and postdoctoral fellows in research in algorithms, statistics, and underlying mathematical topics in algebra and geometry.
|
0.915 |
2016 — 2019 |
Schulman, Leonard |
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information |
Af: Small: Algorithms and Information Theory For Causal Inference @ California Institute of Technology
This project is concerned, firstly, with algorithmic and information-theoretic aspects of Causal Inference. With the exception of some scientific data that is gathered purely for knowledge, most data is gathered for the purpose of potential intervention: this holds for medicine, public health, environmental regulations, market research, legal remedies for discrimination, and in many other domains. A decision-maker cannot take advantage of correlations and other structural characterizations that are discovered in data without knowing about causal relationships between variables. Historically, causality has been teased apart from correlation through controlled experiments. However there are several good reasons that one must often make do with passive observation: ethical reasons; governance constraints; and uniqueness of the system and the inability to re-run history. Absent experiments, we are without the principal arsenal of the scientific method.
Yet there is a special class of systems in which it is possible to perform causality inference purely from passive observation of the statistics. For a system to fall in this class one must be able to establish on physical grounds that certain observable variables are statistically independent of certain others, conditional on a third set being held fixed; the formalism for this is ``semi-Markovian graphical models". It is known which semi-Markovian models fall in this class, subject to the assumption of perfect statistics. From this starting point there remain significant theoretical challenges before these ideas can have the greatest possible impact on practice. Some of the challenges to be addressed include:
(1) The PI will aim to quantify how the stability (condition number) of causal identification depends on the various sources of uncertainty (statistical error; numerical error; model error) and as a function of the structure of the graphical model. The purpose is both to understand what inference is justifiable from existing data, and to impact study design so that data with the greatest leverage is collected. For the former objective, in particular, the PI seeks an efficient algorithm to compute the condition number of a given semi-Markovian model at the specific observed statistics. For the last objective the PI seeks an efficient algorithm to compute the worst-case condition number of a given semi-Markovian model.
(2) Existing causal identification algorithms, applied to data inconsistent with the model (which is unavoidable due to statistical error, and normally also due to model error), will yield an inference inconsistent with the model. The project will help to understand if projection onto the model may improve stability.
(3) One of the obstacles to use of existing methods is that they require sample size exponential in the size of the graphical model. The project aims to determine when it is possible to infer causality using only the marginal distributions over small subsets of the observable variables; this will reduce sample size and likely improve condition number.
(4) In the majority of semi-Markovian models, causality is not identifiable. This leaves open however the possibility of determining (or giving a nontrivial outer bound for) the feasible interval of causal effects. No effective algorithm is currently known for this problem, and we wish to provide one. Such an algorithm could be used to show that an intervention is favorable despite the effect not being fully identifiable.
(5) The project aims to lift the causal-inference algorithm to time series, as well as study the connections with the distinct techniques (Granger causality and Massey's directed information) normally used in this setting.
Secondary emphases of the project include broader research in theoretical computer science. In particular, studying connections between ``boosting" or ``multiplicative weights" methods used in algorithms and machine learning, and their variants which arise out of selection or self-interest in the system dynamics of ecosystems (``weak selection") and economic marketplaces (``tatonnement").
Inseparably from the research effort, the PI will train students and postdocs in these and related areas of the theory of computation.
|
0.915 |
2019 — 2022 |
Schulman, Leonard |
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information |
Nsf-Bsf: Af: Small: Identifying Functional Structure in Data @ California Institute of Technology
Algorithms for unsupervised learning tasks are in constant use in science, engineering, medical research, etc. Progress in optimization procedures for these problems has therefore the potential for very wide adoption. One of the primary research topics of this award is unsupervised learning methods for determining causal effect in scenarios where one cannot, for practical or ethical reasons, perform controlled experiments. At present, the theory for deducing causal effects is somewhat brittle, since it relies upon unrealistic accuracy in the mathematical modeling, and, for large systems, upon unrealistic sample sizes. Scientists therefore do not have very reliable ways of advising the public about "what-if" scenarios. This research aims to provide, and characterize the performance of, causal-identification algorithms with the following goals: (a) Algorithms that work under weaker assumptions than current theory makes (in particular regarding the fidelity of the model to reality), yet deliver still-useful guarantees; (b) Algorithms that work under stronger structural assumptions than current theory makes and can use smaller sample sizes as a result. A related research topic concerns approximation algorithms, and inapproximability bounds, for optimization problems such as data clustering and learning of mixture models. The investigator will train students and postdocs in these and related areas of the theory of computation.
Causal-inference problems will be addressed through the framework of directed probabilistic graphical models. Existing causal-identification algorithms operate with a naive parameter size because, for N-variate graphical models, the complexity parameter (and sample complexity) is exponential in N. By contrast all algorithmic methods for clustering, for learning mixtures of product distributions, or for topic models regard the dimension (i.e., the number of variables N) as a parameter that should not appear, or at worst appear poly-logarithmically, in the exponent. This project aims to provide algorithms with such complexity; however, this is not only an algorithmic question. The existing characterization of when causal identification is even possible is stated under the assumption that one has access to full knowledge of the joint distribution on the N variables. Therefore a related, statistical but not algorithmic goal is to obtain a characterization of graphical models in which causal inference is possible only from the joint distributions of sets of variables of size small relative to N. A candidate class of such models comes from mixture models, beginning with mixtures of products and extending to mixtures of Markov models. Another question concerns graphical models in which causal identification is not possible, yet the range of causal effects consistent with the data is small. In such cases, an algorithm which bounds the causal effect is an adequate replacement for full identification; providing such guarantees is another goal of this work. Finally, research will focus on clustering with squared Euclidean costs: both on the inapproximability threshold and in improving approximation factors through linear programming relaxations or other methods.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
|
0.915 |