About

Kohei Kishida is an Associate Professor at the Siebel School of Computing and Data Science at the University of Illinois Urbana-Champaign. His teaching includes courses such as Symbolic Logic, Philosophical Foundations of Computer Science, Philosophy of Mathematics, and Advanced Symbolic Logic. His research areas encompass philosophy of logic, philosophy of mathematics, and related fields, contributing to the academic foundation of computing and data science through his expertise in symbolic logic and philosophical inquiry.

Research topics

• Computer Science
• Programming language
• Theoretical computer science
• Quantum mechanics
• Pure mathematics
• Mathematics
• Algorithm

Selected publications

• Proto-Quipper with Reversing and Control

  Electronic Proceedings in Theoretical Computer Science · 2025-08-19

  articleOpen access

  The quantum programming language Quipper supports circuit operations such as reversing and controlling certain quantum circuits.Additionally, Quipper provides a function called with-computed, which can be used to program circuits of the form g; f ; g .The latter is a common pattern in quantum circuit design.One benefit of using with-computed, as opposed to constructing the circuit g; f ; g directly from g, f , and g , is that it facilitates an important optimization.Namely, if the resulting circuit is later controlled, only f needs to be controlled; the circuits g and g need not even be controllable.In this paper, we formalize a semantics for reversible and controllable circuits, using a dagger symmetric monoidal category R to interpret reversible circuits, and a new notion we call a controllable category N, which encompasses the control and with-computed operations in Quipper.We extend the language Proto-Quipper with reversing, control and the with-computed operation.Since not all circuits are reversible and/or controllable, we use a type system with modalities to track reversibility and controllability.This generalizes the modality of Fu-Kishida-Ross-Selinger 2023.We give an abstract categorical semantics, and show that the type system and operational semantics are sound with respect to this semantics.

  PublisherOA PDFDOI

• Topology and Justified True Belief: A Baseless, Evidence-Free (and Pointless) Approach

  Lecture notes in computer science · 2024-01-01

  book-chapter1st authorCorresponding
  PublisherDOI

• Proto-Quipper with Reversing and Control

  arXiv (Cornell University) · 2024-10-29 · 1 citations

  preprintOpen access

  The quantum programming language Quipper supports circuit operations such as reversing and controlling certain quantum circuits. Additionally, Quipper provides a function called with-computed, which can be used to program circuits of the form g; f; g-dagger. The latter is a common pattern in quantum circuit design. One benefit of using with-computed, as opposed to constructing the circuit g ; f; g-dagger directly from g, f, and g-dagger, is that it facilitates an important optimization. Namely, if the resulting circuit is later controlled, only f needs to be controlled; the circuits g and g-dagger need not even be controllable. In this paper, we formalize a semantics for reversible and controllable circuits, using a dagger symmetric monoidal category R to interpret reversible circuits, and a new notion we call a controllable category N, which encompasses the control and with-computed operations in Quipper. We extend the language Proto-Quipper with reversing, control and the with-computed operation. Since not all circuits are reversible and/or controllable, we use a type system with modalities to track reversibility and controllability. This generalizes the modality of Fu-Kishida-Ross-Selinger 2023. We give an abstract categorical semantics, and show that the type system and operational semantics are sound with respect to this semantics.

  PublisherOA PDFDOI

• Gödel, Escher, Bell: Contextual Semantics of Logical Paradoxes

  Outstanding contributions to logic · 2023-01-01 · 1 citations

  book-chapter1st authorCorresponding
  PublisherDOI

• A Biset-Enriched Categorical Model for Proto-Quipper with Dynamic Lifting

  Electronic Proceedings in Theoretical Computer Science · 2023-11-14 · 3 citations

  articleOpen access

  Quipper and Proto-Quipper are a family of quantum programming languages that, by their nature as circuit description languages, involve two runtimes: one at which the program generates a circuit and one at which the circuit is executed, normally with probabilistic results due to measurements. Accordingly, the language distinguishes two kinds of data: parameters, which are known at circuit generation time, and states, which are known at circuit execution time. Sometimes, it is desirable for the results of measurements to control the generation of the next part of the circuit. Therefore, the language needs to turn states, such as measurement outcomes, into parameters, an operation we call dynamic lifting. The goal of this paper is to model this interaction between the runtimes by providing a general categorical structure enriched in what we call "bisets". We demonstrate that the biset-enriched structure achieves a proper semantics of the two runtimes and their interaction, by showing that it models a variant of Proto-Quipper with dynamic lifting. The present paper deals with the concrete categorical semantics of this language, whereas a companion paper deals with the syntax, type system, operational semantics, and abstract categorical semantics.

  PublisherOA PDFDOI

• Modalities in the Type Theory of Quantum Programming

  Electronic Proceedings in Theoretical Computer Science · 2023-08-01

  articleOpen access1st authorCorresponding
  PublisherDOI

• Proto-Quipper with Dynamic Lifting

  Proceedings of the ACM on Programming Languages · 2023-01-09 · 17 citations

  articleOpen access

  Quipper is a functional programming language for quantum computing. Proto-Quipper is a family of languages aiming to provide a formal foundation for Quipper. In this paper, we extend Proto-Quipper-M with a construct called dynamic lifting , which is present in Quipper. By virtue of being a circuit description language, Proto-Quipper has two separate runtimes: circuit generation time and circuit execution time. Values that are known at circuit generation time are called parameters , and values that are known at circuit execution time are called states . Dynamic lifting is an operation that enables a state, such as the result of a measurement, to be lifted to a parameter, where it can influence the generation of the next portion of the circuit. As a result, dynamic lifting enables Proto-Quipper programs to interleave classical and quantum computation. We describe the syntax of a language we call Proto-Quipper-Dyn. Its type system uses a system of modalities to keep track of the use of dynamic lifting. We also provide an operational semantics, as well as an abstract categorical semantics for dynamic lifting based on enriched category theory. We prove that both the type system and the operational semantics are sound with respect to our categorical semantics. Finally, we give some examples of Proto-Quipper-Dyn programs that make essential use of dynamic lifting.

  PublisherOA PDFDOI

• Proceedings of the Fourth International Conference on Applied Category Theory

  Electronic Proceedings in Theoretical Computer Science · 2022-10-31

  paratextOpen access1st authorCorresponding

  The Fourth International Conference on Applied Category Theory took place at the Computer Laboratory of the University of Cambridge on 12--16 July 2021. It was a hybrid event, with physical attendees present in Cambridge and other participants taking part online. All the talks were recorded and the videos have been posted online, links to which can be found on the conference website (https://www.cl.cam.ac.uk/events/act2021/). Continuing the trend in the previous meetings of ACT, the contributions to ACT 2021 ranged from pure to applied and represented a great variety of categorical techniques and application topics, including: graphical calculi; lenses; differential categories; categorical probability theory; machine learning; game theory; cybernetics; natural language semantics and processing; cryptography; and finite model theory. This proceedings volume contains about half of the papers that were presented as talks at ACT 2021. This selection is a reflection of the authors' choice as to whether to publish their papers in this volume or elsewhere.

  PublisherDOI

• On the Lambek embedding and the category of product-preserving presheaves

  arXiv (Cornell University) · 2022-05-12

  preprintOpen access

  It is well-known that the category of presheaf functors is complete and cocomplete, and that the Yoneda embedding into the presheaf category preserves products. However, the Yoneda embedding does not preserve coproducts. It is perhaps less well-known that if we restrict the codomain of the Yoneda embedding to the full subcategory of limit-preserving functors, then this embedding preserves colimits, while still enjoying most of the other useful properties of the Yoneda embedding. We call this modified embedding the Lambek embedding. The category of limit-preserving functors is known to be a reflective subcategory of the category of all functors, i.e., there is a left adjoint for the inclusion functor. In the literature, the existence of this left adjoint is often proved non-constructively, e.g., by an application of Freyd's adjoint functor theorem. In this paper, we provide an alternative, more constructive proof of this fact. We first explain the Lambek embedding and why it preserves coproducts. Then we review some concepts from multi-sorted algebras and observe that there is a one-to-one correspondence between product-preserving presheaves and certain multi-sorted term algebras. We provide a construction that freely turns any presheaf functor into a product-preserving one, hence giving an explicit definition of the left adjoint functor of the inclusion. Finally, we sketch how to extend our method to prove that the subcategory of limit-preserving functors is also reflective.

  PublisherOA PDFDOI

• Proceedings of the Fourth International Conference on Applied Category Theory

  Electronic Proceedings in Theoretical Computer Science · 2022-10-31 · 1 citations

  articleOpen access1st authorCorresponding
  PublisherDOI

Frequent coauthors

• Peter Selinger

  14 shared

• Shane Mansfield

  14 shared

• Rui Soares Barbosa

  International Iberian Nanotechnology Laboratory

  13 shared

• Samson Abramsky

  University College London

  13 shared

• Neil J. Ross

  Dalhousie University

  11 shared

• Peng Fu

  Dalhousie University

  10 shared

• Giovanni Carù

  University of Oxford

  8 shared

• Raymond Lal

  7 shared

Labs

• Siebel School of Computing and Data SciencePI

Education

• Ph.D., Computer Science

  University of Illinois at Urbana-Champaign

  2009

• M.S., Computer Science

  University of Illinois at Urbana-Champaign

  2005

• B.S., Computer Science

  University of Tokyo

  2003