Robert Rand

Robert Rand

Auto-generated profile, based on publicly available information

Robert Rand

University of Chicago, Chicago, USA

Research Focus & Metrics

Academic Career Length

14Years (2013-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
4 January 2021 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
KHKesha Hietala
Kesha Hietala
RRRobert Rand
Robert Rand
SHShih-Han Hung
Shih-Han Hung
XWXiaodi Wu
Xiaodi Wu
MHMichael Hicks
Michael Hicks
We present VOQC, the first fully verified optimizer for quantum circuits, written using the Coq proof assistant. Quantum circuits are expressed as programs in a simple, low-level language called SQIR, a simple quantum intermediate representation, which is deeply embedded in Coq. Optimizations and other transformations are expressed as Coq functions, which are proved correct with respect to a semantics of SQIR programs. SQIR uses a semantics of matrices of complex numbers, which is the standard for quantum computation, but treats matrices symbolically in order to reason about programs that use an arbitrary number of quantum bits. SQIR's careful design and our provided automation make it possible to write and verify a broad range of optimizations in VOQC, including full-circuit transformations from cutting-edge optimizers.

1 January 2017
Verified
Conference Paper
Open access
JPJennifer Paykin
Jennifer Paykin
RRRobert Rand
Robert Rand
SZSteve Zdancewic
Steve Zdancewic
This paper introduces QWIRE (``choir''), a language for defining quantum circuits and an interface for manipulating them inside of an arbitrary classical host language. QWIRE is minimal---it contains only a few primitives---and sound with respect to the physical properties entailed by quantum mechanics. At the same time, QWIRE is expressive and highly modular due to its relationship with the host language, mirroring the QRAM model of computation that places a quantum computer (controlled by circuits) alongside a classical computer (controlled by the host language). We present QWIRE along with its type system and operational semantics, which we prove is safe and strongly normalizing whenever the host language is. We give circuits a denotational semantics in terms of density matrices. Throughout, we investigate examples that demonstrate the expressive power of QWIRE, including extensions to the host language that (1) expose a general analysis framework for circuits, and (2) provide dependent types.

9 January 2023 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
FVFinn Voichick
Finn Voichick
LLLiyi Li
Liyi Li
RRRobert Rand
Robert Rand
MHMichael Hicks
Michael Hicks
We introduce Qunity, a new quantum programming language designed to treat quantum computing as a natural generalization of classical computing. Qunity presents a unified syntax where familiar programming constructs can have both quantum and classical effects. For example, one can use sum types to implement the direct sum of linear operators, exception-handling syntax to implement projective measurements, and aliasing to induce entanglement. Further, Qunity takes advantage of the overlooked BQP subroutine theorem, allowing one to construct reversible subroutines from irreversible quantum algorithms through the uncomputation of "garbage" outputs. Unlike existing languages that enable quantum aspects with separate add-ons (like a classical language with quantum gates bolted on), Qunity provides a unified syntax and a novel denotational semantics that guarantees that programs are quantum mechanically valid. We present Qunity's syntax, type system, and denotational semantics, showing how it can cleanly express several quantum algorithms. We also detail how Qunity can be compiled into a low-level qubit circuit language like OpenQASM, proving the realizability of our design.

1 April 2013 in Discrete Applied Mathematics
Verified
Journal Article
Closed access
KAK. Adaricheva
K. Adaricheva
JNJ.B. Nation
J.B. Nation
RRR. Rand
R. Rand

15 May 2023 in Proceedings of the National Academy of Sciences
Verified
Journal Article
Open access
YPYuxiang Peng
Yuxiang Peng
KHKesha Hietala
Kesha Hietala
RTRunzhou Tao
Runzhou Tao
LLLiyi Li
Liyi Li
RRRobert Rand
Robert Rand
XWXiaodi Wu
Xiaodi Wu
Quantum computing technology may soon deliver revolutionary improvements in algorithmic performance, but it is useful only if computed answers are correct. While hardware-level decoherence errors have garnered significant attention, a less recognized obstacle to correctness is that of human programming errors—“bugs.” Techniques familiar to most programmers from the classical domain for avoiding, discovering, and diagnosing bugs do not easily transfer, at scale, to the quantum domain because of its unique characteristics. To address this problem, we have been working to adapt formal methods to quantum programming. With such methods, a programmer writes a mathematical specification alongside the program and semiautomatically proves the program correct with respect to it. The proof’s validity is automatically confirmed—certified—by a “proof assistant.” Formal methods have successfully yielded high-assurance classical software artifacts, and the underlying technology has produced certified proofs of major mathematical theorems. As a demonstration of the feasibility of applying formal methods to quantum programming, we present a formally certified end-to-end implementation of Shor’s prime factorization algorithm, developed as part of a framework for applying the certified approach to general applications. By leveraging our framework, one can significantly reduce the effects of human errors and obtain a high-assurance implementation of large-scale quantum applications in a principled way.

1 December 2015 in Electronic Notes in Theoretical Computer Science
Verified
Journal Article
Open access
RRRobert Rand
Robert Rand
SZSteve Zdancewic
Steve Zdancewic
We introduce a Hoare-style logic for probabilistic programs, called VPHL, that has been formally verified in the Coq proof assistant. VPHL features propositional, rather than additive, assertions and a simple set of rules for reasoning about these assertions using the standard axioms of probability theory. VPHL's assertions are partial correctness assertions, meaning that their conclusions are dependent upon (deterministic) program termination. The underlying simple probabilistic imperative language, PrImp, includes a probabilistic toss operator, probabilistic guards and potentially-non-terminating while loops