Quantum First-Order Logics That Capture Logarithmic-Time/Space Quantum Computability

• URL: http://arxiv.org/abs/2501.12007v1
• Date: Tue, 21 Jan 2025 09:58:59 GMT
• Title: Quantum First-Order Logics That Capture Logarithmic-Time/Space Quantum Computability
• Authors: Tomoyuki Yamakami,
• Abstract summary: This work is to express "quantum computation" by introducing specially-featured quantum connectives and quantum quantifiers. We demonstrate that quantum first-order logics possess an ability of expressing bounded-error quantum logarithmic-time computability.
• Score: 0.0
• License:
• Abstract: We introduce a quantum analogue of classical first-order logic (FO) and develop a theory of quantum first-order logic as a basis of the productive discussions on the power of logical expressiveness toward quantum computing. The purpose of this work is to logically express "quantum computation" by introducing specially-featured quantum connectives and quantum quantifiers that quantify fixed-dimensional quantum states. Our approach is founded on the recently introduced recursion-theoretical schematic definitions of time-bounded quantum functions, which map finite-dimensional Hilbert spaces to themselves. The quantum first-order logic (QFO) in this work therefore looks quite different from the well-known old concept of quantum logic based on lattice theory. We demonstrate that quantum first-order logics possess an ability of expressing bounded-error quantum logarithmic-time computability by the use of new "functional" quantum variables. In contrast, an extra inclusion of quantum transitive closure operator helps us characterize quantum logarithmic-space computability. The same computability can be achieved by the use of different "functional" quantum variables.

Related papers

• Universal Quantum Computation via Superposed Orders of Single-Qubit Gates [6.652619295281611]
  We prove that any two-qubit controlled quantum gate can be deterministically realized. Superposed orders of single-qubit gates can enable universal quantum computation.
  arXiv  Detail & Related papers  (2023-11-22T19:10:57Z)
• Quantum data learning for quantum simulations in high-energy physics [55.41644538483948]
  We explore the applicability of quantum-data learning to practical problems in high-energy physics. We make use of ansatz based on quantum convolutional neural networks and numerically show that it is capable of recognizing quantum phases of ground states. The observation of non-trivial learning properties demonstrated in these benchmarks will motivate further exploration of the quantum-data learning architecture in high-energy physics.
  arXiv  Detail & Related papers  (2023-06-29T18:00:01Z)
• The wave-particle duality of the qudit quantum space and the quantum wave gates [0.0]
  We first study the quantum functionals whose relation to the quantum states is analogous to that between the momentum and position wavefunctions in fundamental quantum physics. Connecting the partition interpretation of the qudit functionals to the effects of quantum gates we classify all elementary quantum gates by ordered pairs of qudit functionals. By generalizing the qudit functionals to quantum functionals, the new type of "quantum wave gates" are discovered as quantum versions of the conventional quantum gates.
  arXiv  Detail & Related papers  (2022-07-11T22:16:33Z)
• On the Common Logical Structure of Classical and Quantum Mechanics [0.0]
  We show that quantum theory does satisfy the classical distributivity law once the full meaning of quantum propositions is properly taken into account. We show that the lattice of statistical propositions in classical mechanics follows the same structure, yielding an analogue non-commutative sublattice of classical propositions.
  arXiv  Detail & Related papers  (2022-06-21T18:31:53Z)
• Birkhoff-von Neumann Quantum Logic as an Assertion Language for Quantum Programs [1.1878820609988696]
  A first-order logic with quantum variables is needed as an assertion language for specifying and reasoning about various properties of quantum programs. In this paper, we introduce a first-order extension of Birkhoff-von Neumann quantum logic with universal and existential quantifiers over quantum variables.
  arXiv  Detail & Related papers  (2022-05-04T08:57:44Z)
• LQP: The Dynamic Logic of Quantum Information [77.34726150561087]
  This paper introduces a dynamic logic formalism for reasoning about information flow in composite quantum systems. We present a finitary syntax, a relational semantics and a sound proof system for this logic. As applications, we use our system to give formal correctness for the Teleportation protocol and for a standard Quantum Secret Sharing protocol.
  arXiv  Detail & Related papers  (2021-10-04T12:20:23Z)
• The Logic of Quantum Programs [77.34726150561087]
  We present a logical calculus for reasoning about information flow in quantum programs. In particular we introduce a dynamic logic that is capable of dealing with quantum measurements, unitary evolutions and entanglements in compound quantum systems.
  arXiv  Detail & Related papers  (2021-09-14T16:08:37Z)
• Efficient criteria of quantumness for a large system of qubits [58.720142291102135]
  We discuss the dimensionless combinations of basic parameters of large, partially quantum coherent systems. Based on analytical and numerical calculations, we suggest one such number for a system of qubits undergoing adiabatic evolution.
  arXiv  Detail & Related papers  (2021-08-30T23:50:05Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
  Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems. We propose an algorithm to implement imaginary time propagation on a quantum computer.
  arXiv  Detail & Related papers  (2021-02-24T12:48:00Z)
• A Quantum Interpretation of Bunched Logic for Quantum Separation Logic [22.507329566323982]
  We develop a program logic where pre- and post-conditions are BI formulas describing quantum states. We exercise the logic for proving the security of quantum one-time pad and secret sharing.
  arXiv  Detail & Related papers  (2021-01-30T22:24:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.