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

IEEE International Conference on Nanotechnology (IEEE-NANO)

Quantum switching and quantum string matching

Tien-Sheng Lin, Chin-Yung Lu, Sy‐Yen Kuo

Published Aug 1, 2010• 6 citations
Publisher

Abstract

Applications of quantum string matching can be found in quantum signature scheme and quantum fingerprinting. The major benefit of these applications is computation complexity. Quantum Boolean circuits can check the equivalence function: all in puts are quantum digital state. However, it is difficult to verify quantum strings if all input qubits are quantum superposition state. Quantum switching could be reversible circuits. These circuits have two major benefits: information lossless and energy saving. In this paper, we use quantum circuits to design the control module that can verify the equivalence of quantum strings and satisfy the following condition: all inputs qubits could be quantum superposition state. In the pro posed circuits, the control module can form a special correlation between input sequence and output sequence. This correlation can design the equivalence function of quantum strings to solve the problem: input strings with superposition. In regard to the performance, the scalability of the proposed circuits can be achieved.

DOI
10.1109/nano.2010.5697866

Related papers

Quantum blind signature based on quantum circuit

Tien-Sheng Lin, Yanlin Chen, Ting-Hsu Chang +2 more

Quantum circuit is a reversible circuit that can be designed the control module to derive the correlation between quantum input sequence and quantum output sequence. In addition, in this paper we use the control module of the quantum circuit to verify the equivalence of the quantum state such that quantum blind signature can achieve the security requirement of the signature scheme and resist eavesdropping from the outsider. The core concept of the proposed signature is based on the correlation of quantum entangled state to investigate that the message string and the signatory string is consistent. In regard to the security, the blindness and the failure of eavesdropping can be preserved by this work. The proposed signature can achieve impossibility of forgery and impossibility of disavowal.

IEEE International Conference on Nanotechnology (IEEE-NANO)•Aug 1, 2014•7 citations

Quantum Circuits for Fixed Substring Matching Problems

Domenico Aldo Cantone, Simone Faro, Arianna Pavone +1 more

Quantum computation represents a computational paradigm whose distinctive attributes confer the ability to devise algorithms with asymptotic performance levels significantly superior to those achievable via classical computation. Recent strides have been taken to apply this computational framework in tackling and resolving various issues related to text processing. The resultant solutions demonstrate marked advantages over their classical counterparts. This study employs quantum computation to efficaciously surmount text processing challenges, particularly those involving string comparison. The focus is on the alignment of fixed-length substrings within two input strings. Specifically, given two input strings, $x$ and $y$, both of length $n$, and a value $d \leq n$, we want to verify the following conditions: the existence of a common prefix of length $d$, the presence of a common substring of length $d$ beginning at position $j$ (with $0 \leq j < n$) and, the presence of any common substring of length $d$ beginning in both strings at the same position. Such problems find applications as sub-procedures in a variety of problems concerning text processing and sequence analysis. Notably, our approach furnishes polylogarithmic solutions, a stark contrast to the linear complexity inherent in the best classical alternatives.

arXiv:2308.11758•Aug 22, 2023•2 citations

Reversible quantum circuits and quantum transmission integrity

Tien-Sheng Lin, Chia-Hung Chien, Ting-Hsu Chang +2 more

This paper proposes a novel work to design reversible quantum circuits. The function of this circuit is to investigate quantum transmission integrity in the quantum communication networks. This work is to verify quantum transmission sequence of a quantum frame by using reversible quantum model. This model designs control module to derive the correlation between two quantum strings: quantum input sequence and quantum output sequence. If a quantum frame reserves the correlation, then we can obtain quantum transmission sequence. So, quantum transmission integrity of a quantum frame can be verified.

IEEE International Conference on Nanotechnology (IEEE-NANO)•Aug 1, 2011•3 citations

Boolean Matching Reversible Circuits: Algorithm and Complexity

Tian-Fu Chen, Jie-Hong Roland Jiang

Boolean matching is an important problem in logic synthesis and verification. Despite being well-studied for conventional Boolean circuits, its treatment for reversible logic circuits remains largely, if not completely, missing. This work provides the first such study. Given two (black-box) reversible logic circuits that are promised to be matchable, we check their equivalences under various input/output negation and permutation conditions subject to the availability/unavailability of their inverse circuits. Notably, among other results, we show that the equivalence up to input negation and permutation is solvable in quantum polynomial time, while its classical complexity is exponential. This result is arguably the first demonstration of quantum exponential speedup in solving design automation problems. Also, as a negative result, we show that the equivalence up to both input and output negations is not solvable in quantum polynomial time unless UNIQUE-SAT is, which is unlikely. This work paves the theoretical foundation of Boolean matching reversible circuits for potential applications, e.g., in quantum circuit synthesis.

arXiv:2404.12184•ACM/IEEE Design Automation Conference (DAC)•Jun 23, 2024•4 citations

Checking equivalence of quantum circuits and states

George F. Viamontes, Igor L. Markov, John P. Hayes

Among the post-CMOS technologies currently under investigation, quantum computing (QC) holds a special place. QC offers not only extremely small size and low power, but also exponential speed-ups for important simulation and optimization problems. It also poses new CAD problems that are similar to. but more challenging, than the related problems in classical (non-quantum) CAD. such as determining if two states or circuits are functionally equivalent. While differences in classical states are easy to detect, quantum states, which are represented by complex-valued vectors, exhibit subtle differences leading to several notions of equivalence. This provides flexibility in optimizing quantum circuits, but leads to difficult new equivalence-checking issues for simulation and synthesis. We identify several different equivalence-checking problems and present algorithms for practical benchmarks, including quantum communication and search circuits, which are shown to be very fast and robust for hundreds of qubits.

arXiv:0705.0017•Digest of technical papers/Digest of technical papers - IEEE/ACM International Conference on Computer-Aided Design•Nov 1, 2007•76 citations

An efficient functional verification method for quantum boolean circuits

Shiou-An Wang, Chin-Yung Lu, Sy‐Yen Kuo

Functional verification is an important design method for verifying functional equivalence between a simplified quantum Boolean circuit and original one. During the design process, checking the equivalence of two quantum Boolean circuits is necessary. In this paper, we present an algorithm that can efficiently and easily verify two quantum Boolean circuits by using the back propagation method. For a set of input vectors, the idea of the algorithm is to find the checking vectors that output vectors are different from input vectors by a backward tracking process.

IEEE Conference on Nanotechnology (IEEE NANO)•Apr 1, 2005•0 citations
Applications of quantum string matching can be found in quantum signature scheme and quantum fingerprinting. The major benefit of these applications is computation complexity. Quantum Boolean circuits can check the equivalence function: all in puts are quantum digital state. However, it is difficult to verify quantum strings if all input qubits are quantum superposition state. Quantum switching could be reversible circuits. These circuits have two major benefits: information lossless and energy saving. In this paper, we use quantum circuits to design the control module that can verify the equivalence of quantum strings and satisfy the following condition: all inputs qubits could be quantum superposition state. In the pro posed circuits, the control module can form a special correlation between input sequence and output sequence. This correlation can design the equivalence function of quantum strings to solve the problem: input strings with superposition. In regard to the performance, the scalability of the proposed circuits can be achieved.
Quantum circuit is a reversible circuit that can be designed the control module to derive the correlation between quantum input sequence and quantum output sequence. In addition, in this paper we use the control module of the quantum circuit to verify the equivalence of the quantum state such that quantum blind signature can achieve the security requirement of the signature scheme and resist eavesdropping from the outsider. The core concept of the proposed signature is based on the correlation of quantum entangled state to investigate that the message string and the signatory string is consistent. In regard to the security, the blindness and the failure of eavesdropping can be preserved by this work. The proposed signature can achieve impossibility of forgery and impossibility of disavowal.
Quantum computation represents a computational paradigm whose distinctive attributes confer the ability to devise algorithms with asymptotic performance levels significantly superior to those achievable via classical computation. Recent strides have been taken to apply this computational framework in tackling and resolving various issues related to text processing. The resultant solutions demonstrate marked advantages over their classical counterparts. This study employs quantum computation to efficaciously surmount text processing challenges, particularly those involving string comparison. The focus is on the alignment of fixed-length substrings within two input strings. Specifically, given two input strings, xxx and yyy, both of length nnn, and a value d≤nd \leq nd≤n, we want to verify the following conditions: the existence of a common prefix of length ddd, the presence of a common substring of length ddd beginning at position jjj (with 0≤j<n0 \leq j < n0≤j<n) and, the presence of any common substring of length ddd beginning in both strings at the same position. Such problems find applications as sub-procedures in a variety of problems concerning text processing and sequence analysis. Notably, our approach furnishes polylogarithmic solutions, a stark contrast to the linear complexity inherent in the best classical alternatives.
This paper proposes a novel work to design reversible quantum circuits. The function of this circuit is to investigate quantum transmission integrity in the quantum communication networks. This work is to verify quantum transmission sequence of a quantum frame by using reversible quantum model. This model designs control module to derive the correlation between two quantum strings: quantum input sequence and quantum output sequence. If a quantum frame reserves the correlation, then we can obtain quantum transmission sequence. So, quantum transmission integrity of a quantum frame can be verified.
Boolean matching is an important problem in logic synthesis and verification. Despite being well-studied for conventional Boolean circuits, its treatment for reversible logic circuits remains largely, if not completely, missing. This work provides the first such study. Given two (black-box) reversible logic circuits that are promised to be matchable, we check their equivalences under various input/output negation and permutation conditions subject to the availability/unavailability of their inverse circuits. Notably, among other results, we show that the equivalence up to input negation and permutation is solvable in quantum polynomial time, while its classical complexity is exponential. This result is arguably the first demonstration of quantum exponential speedup in solving design automation problems. Also, as a negative result, we show that the equivalence up to both input and output negations is not solvable in quantum polynomial time unless UNIQUE-SAT is, which is unlikely. This work paves the theoretical foundation of Boolean matching reversible circuits for potential applications, e.g., in quantum circuit synthesis.
Among the post-CMOS technologies currently under investigation, quantum computing (QC) holds a special place. QC offers not only extremely small size and low power, but also exponential speed-ups for important simulation and optimization problems. It also poses new CAD problems that are similar to. but more challenging, than the related problems in classical (non-quantum) CAD. such as determining if two states or circuits are functionally equivalent. While differences in classical states are easy to detect, quantum states, which are represented by complex-valued vectors, exhibit subtle differences leading to several notions of equivalence. This provides flexibility in optimizing quantum circuits, but leads to difficult new equivalence-checking issues for simulation and synthesis. We identify several different equivalence-checking problems and present algorithms for practical benchmarks, including quantum communication and search circuits, which are shown to be very fast and robust for hundreds of qubits.
Functional verification is an important design method for verifying functional equivalence between a simplified quantum Boolean circuit and original one. During the design process, checking the equivalence of two quantum Boolean circuits is necessary. In this paper, we present an algorithm that can efficiently and easily verify two quantum Boolean circuits by using the back propagation method. For a set of input vectors, the idea of the algorithm is to find the checking vectors that output vectors are different from input vectors by a backward tracking process.