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.
more »
« less
Snowflake: Supporting Programming and Proofs
Rigorous, mathematical reasoning, i.e., proof, is the foundation of any undergraduate computer science education. However, students find mathematical proof exceedingly challenging, but also at the same time do not see its relevance to programming. We address these concerns with Snowflake, an educational proof assistant designed to help undergraduates overcome these difficulties when authoring mathematical proof. Snowflake does this by operating in a context where mathematical proof is introduced alongside programming in either a CS1 or CS2 context. The lens that we use to unite the two concepts is program correctness, a topic that immediately makes relevant the concept of formal reasoning as students are perpetually faced with the issue of whether their code is correct.
Snowflake is a proof assistant designed for the needs of undergraduates in courses that closely time programming and proof. It is a web-based application that helps students author proofs not only in the context of program correctness in-the-small, but also other topics found in discrete mathematics courses. We report on the design of Snowflake, the kinds of reasoning it enables, and our plans to deploy Snowflake in the classroom.
more »
« less
- Award ID(s):
- 2049911
- PAR ID:
- 10404383
- Date Published:
- Journal Name:
- SIGCSE 2023: Proceedings of the 54th ACM Technical Symposium on Computer Science Education
- Volume:
- 2
- Page Range / eLocation ID:
- 1398
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In transition to proof courses for undergraduates, we conducted teaching experiments supporting students to learn logic and proofs rooted in set-based meanings. We invited students to reason about sets using three representational systems: set notation (including symbolic expressions and set-builder notation), mathematical statements (largely in English), and Euler diagrams. In this report, we share evidence regarding how these three representations provided students with tools for reasoning and communicating about set relationships to explore the logic of statements. By analyzing student responses to tasks that asked them to translate between the representational systems, we gain insight into the accessibility and productivity of these tools for such instruction.more » « less
-
null (Ed.)We verify the functional correctness of an array-of-bins (segregated free-lists) single-thread malloc/free system with respect to a correctness specification written in separation logic. The memory allocator is written in standard C code compatible with the standard API; the specification is in the Verifiable C program logic, and the proof is done in the Verified Software Toolchain within the Coq proof assistant. Our "resource-aware" specification can guarantee when malloc will successfully return a block, unlike the standard Posix specification that allows malloc to return NULL whenever it wants to. We also prove subsumption (refinement): the resource-aware specification implies a resource-oblivious spec.more » « less
-
Cook, S. ; Katz, B. ; Moore-Russo D. (Ed.)Learning to interpret proofs is an important milepost in the maturity and development of students of higher mathematics. A key learning objective in proof-based courses is to discern whether a given proof is a valid justification of its underlying claim. In this study, we presented students with conditional statements and associated proofs and asked them to determine whether the proofs proved the statements and to explain their reasoning. Prior studies have found that inexperienced provers often accept the proof of a statement’s converse and reject proofs by contraposition, which are both erroneous determinations. Our study contributes to the literature by corroborating these findings and suggesting a connection between students’ reading comprehension and proof validation behaviors and their beliefs about mathematical proof and mathematical knowledge base.more » « less
-
Interactive proof assistants are computer programs carefully constructed to check a human-designed proof of a mathematical claim with high confidence in the implementation. However, this only validates truth of a formal claim, which may have been mistranslated from a claim made in natural language. This is especially problematic when using proof assistants to formally verify the correctness of software with respect to a natural language specification. The translation from informal to formal remains a challenging, time-consuming process that is difficult to audit for correctness. This paper shows that it is possible to build support for specifications written in expressive subsets of natural language, within existing proof assistants, consistent with the principles used to establish trust and auditability in proof assistants themselves. We implement a means to provide specifications in a modularly extensible formal subset of English, and have them automatically translated into formal claims, entirely within the Lean proof assistant. Our approach is extensible (placing no permanent restrictions on grammatical structure), modular (allowing information about new words to be distributed alongside libraries), and produces proof certificates explaining how each word was interpreted and how the sentence's structure was used to compute the meaning. We apply our prototype to the translation of various English descriptions of formal specifications from a popular textbook into Lean formalizations; all can be translated correctly with a modest lexicon with only minor modifications related to lexicon size.more » « less