Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2501.12007 · Lecture notes in computer science

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

Tomoyuki Yamakami

Published Jan 1, 2024• 1 citation
arXivHTMLPDF
DOI
10.1007/978-3-031-64309-5_25

Related papers

Purely-logarithmic-time- and constant-space-overhead fault-tolerant quantum computation

Zhengyi Han, Zi-Wen Liu

We prove that constant-space-overhead fault-tolerant quantum computation can be achieved with provably strictly logarithmic time overhead, improving over the best known results with additional subpolylogarithmic factors. Our main construction uses polynomial-subrank transversal logical $\CCZ$ gates on good quantum locally testable codes to implement addressable universal computation by transferring batches of logical qubits between dense storage and active logical subspaces while reusing the same ancillary workspace. Logical $\CCZ$ gates are implemented directly by the transversal operation, so only stabilizer resource states require separate preparation. Furthermore, we give an alternative construction that also achieves purely logarithmic time overhead based on modifying the quantum Reed--Solomon magic-state distillation scheme of Nguyen and Pattison. Recursively applying a fixed distillation circuit protected by qLTCs of increasing block length eliminates the subpolylogarithmic time factor.

quant-pharXiv:2609.28461•Sep 24, 2026•0 citations

Expressing Power of Elementary Quantum Recursion Schemes for Quantum Logarithmic-Time Computability

Tomoyuki Yamakami

Lecture notes in computer science•Jan 1, 2022•1 citation

Quantum Computational Logics and Possible Applications

María Luisa Dalla Chiara, Roberto Giuntini, Roberto Leporini +1 more

International Journal of Theoretical Physics•Jul 27, 2007•3 citations

Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states

Mariami Gachechiladze, Otfried Gühne, Akimasa Miyake

While the circuit model of quantum computation defines its logical depth or ``computational time'' in terms of temporal gate sequences, the measurement-based model could allow totally different temporal ordering and parallelization of logical gates. By developing techniques to analyze Pauli measurements on multiqubit hypergraph states generated by the controlled-controlled-Z (ccz) gates, we introduce a deterministic scheme of universal measurement-based computation. In contrast to the cluster-state scheme where the Clifford gates are parallelizable, our scheme enjoys massive parallelization of ccz and swap gates, so that the computational depth grows with the number of global applications of Hadamard gates, or, in other words, with the number of changing computational bases. A logarithmic-depth implementation of an $N$-times controlled-Z gate illustrates a trade-off between space and time complexity.

arXiv:1805.12093•Physical Review A•May 2, 2019•39 citations

Relaxation times do not capture logical qubit dynamics

Pal, Amit, R. Blatt, Thomas Monz +5 more

Quantum error correction procedures have the potential to enable faithful operation of large-scale quantum computers.They protect information from environmental decoherence by storing it in logical qubits, built from ensembles of entangled physical qubits according to suitably tailored quantum error correcting encodings.To date, no generally accepted framework to characterise the behaviour of logical qubits as quantum memories has been developed.In this work, we show that generalisations of well-established figures of merit of physical qubits, such as relaxation times, to logical qubits fail and do not capture dynamics of logical qubits.We experimentally illustrate that, in particular, spatial noise correlations can give rise to rich and counter-intuitive dynamical behavior of logical qubits.We show that a suitable set of observables, formed by code space population and logical operators within the code space, allows one to track and characterize the dynamical behaviour of logical qubits.Awareness of these effects and the efficient characterisation tools used in this work will help to guide and benchmark experimental implementations of logical qubits.

•Jan 1, 2022•9 citations

Concrete and abstract quantum computational logics

María Luisa Dalla Chiara, Roberto Giuntini, Roberto Leporini

•Jan 1, 2007•0 citations
We prove that constant-space-overhead fault-tolerant quantum computation can be achieved with provably strictly logarithmic time overhead, improving over the best known results with additional subpolylogarithmic factors. Our main construction uses polynomial-subrank transversal logical $\CCZ$ gates on good quantum locally testable codes to implement addressable universal computation by transferring batches of logical qubits between dense storage and active logical subspaces while reusing the same ancillary workspace. Logical $\CCZ$ gates are implemented directly by the transversal operation, so only stabilizer resource states require separate preparation. Furthermore, we give an alternative construction that also achieves purely logarithmic time overhead based on modifying the quantum Reed--Solomon magic-state distillation scheme of Nguyen and Pattison. Recursively applying a fixed distillation circuit protected by qLTCs of increasing block length eliminates the subpolylogarithmic time factor.
While the circuit model of quantum computation defines its logical depth or ``computational time'' in terms of temporal gate sequences, the measurement-based model could allow totally different temporal ordering and parallelization of logical gates. By developing techniques to analyze Pauli measurements on multiqubit hypergraph states generated by the controlled-controlled-Z (ccz) gates, we introduce a deterministic scheme of universal measurement-based computation. In contrast to the cluster-state scheme where the Clifford gates are parallelizable, our scheme enjoys massive parallelization of ccz and swap gates, so that the computational depth grows with the number of global applications of Hadamard gates, or, in other words, with the number of changing computational bases. A logarithmic-depth implementation of an NNN-times controlled-Z gate illustrates a trade-off between space and time complexity.
Quantum error correction procedures have the potential to enable faithful operation of large-scale quantum computers.They protect information from environmental decoherence by storing it in logical qubits, built from ensembles of entangled physical qubits according to suitably tailored quantum error correcting encodings.To date, no generally accepted framework to characterise the behaviour of logical qubits as quantum memories has been developed.In this work, we show that generalisations of well-established figures of merit of physical qubits, such as relaxation times, to logical qubits fail and do not capture dynamics of logical qubits.We experimentally illustrate that, in particular, spatial noise correlations can give rise to rich and counter-intuitive dynamical behavior of logical qubits.We show that a suitable set of observables, formed by code space population and logical operators within the code space, allows one to track and characterize the dynamical behaviour of logical qubits.Awareness of these effects and the efficient characterisation tools used in this work will help to guide and benchmark experimental implementations of logical qubits.