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

Journal of Physics A Mathematical and Theoretical

Designing quantum circuits for decoding binary linear codes

Hyungkee Yoo, Whan-Hyuk Choi, Yoonjin Lee

Published Nov 21, 2024• 3 citations
Publisher

Abstract

Abstract In the coding theory, it is one of the most important research problems to find an efficient algorithm for the decoding process. A quantum computer is an innovative computing device that performs calculations using the principles of quantum mechanics. In this paper, we find a decoding algorithm for binary linear codes using quantum circuits; this is the first time that quantum circuits are used as a main tool for decoding binary linear codes. Our decoding algorithm is mainly based on Grover’s search algorithm. In detail, we study the process of implementing the exhaustive search using quantum circuits for decoding binary linear codes. For our purpose, we design a modified Grover’s algorithm (algorithm 1) using three tools: the matrix multiplier, the Hamming weight counter, and the state indicator. We present algorithm 2, which is a quantum decoding algorithm for binary linear codes. We illustrate algorithm 1 using the [7, 4, 3] Hamming code, and algorithm 2 is implemented by IBM Quantum Composer.

DOI
10.1088/1751-8121/ad955d

Related papers

A quantum algorithm for automata encoding

Edison Tsai, Marek A. Perkowski

Encoding of finite automata or state machines is critical to modern digital logic design methods for sequential circuits. Encoding is the process of assigning to every state, input value, and output value of a state machine a binary string, which is used to represent that state, input value, or output value in digital logic. Usually, one wishes to choose an encoding that, when the state machine is implemented as a digital logic circuit, will optimize some aspect of that circuit. For instance, one might wish to encode in such a way as to minimize power dissipation or silicon area. For most such optimization objectives, no method to find the exact solution, other than a straightforward exhaustive search, is known. Recent progress towards producing a quantum computer of large enough scale to surpass modern supercomputers has made it increasingly relevant to consider how quantum computers may be used to solve problems of practical interest. A quantum computer using Grover?s well-known search algorithm can perform exhaustive searches that would be impractical on a classical computer, due to the speedup provided by Grover?s algorithm. Therefore, we propose to use Grover?s algorithm to find optimal encodings for finite state machines via exhaustive search. We demonstrate the design of quantum circuits that allow Grover?s algorithm to be used for this purpose. The quantum circuit design methods that we introduce are potentially applicable to other problems as well.

Facta universitatis - series Electronics and Energetics•Jan 1, 2020•6 citations

A quantum algorithm for syndrome decoding of classical error-correcting linear block codes

Mainak Bhattacharyya, Ankur Raina

Decoding of linear block codes using syndrome decoding and finding whether there exists a codeword of weight$w$in a set of codewords are known to belong to a class of NP-complete problems. For syndrome decoding of linear block codes, we provide an algorithm that gives a probabilistic solution with least Hamming weight. The algorithm can speed up this process significantly with the help of quantum search algorithm. For this, we make use of a search algorithm inspired from Grover's search. We also suggest a general approach for building a quantum circuit for syndrome detection. We test the algorithm in IBM Quantum Experience using qasm simulator and perform the complexity analysis identifying the algorithm's domain of utility.

IEEE/ACM Symposium on Edge Computing (SEC)•Dec 1, 2022•6 citations

Quantum Channel Decoding

Shahab Hamidi-Rad, John Kaewell

Channel Coding is the technique that enables reliable delivery of digital data over unreliable communication channels. For most high performance channel coding techniques, the existing classical algorithms are computationally expensive, making them impractical for throughput-demanding applications with large code sizes. Today’s Noisy Intermediate-Scale Quantum (NISQ) computers, although limited due to a modest number of qubits, short coherence time, and poor gate fidelity, are useful tools for exploring and experimenting with possible solutions to a wide variety of computational problems.In this paper we show how careful initialization of qubits combined with a simple quantum circuit, enables us to perform channel decoding for different linear block codes. We first explain our novel qubit initialization technique which we call "Quantum Soft Decision". We then show how to build a simple quantum circuit based on the Generator or Parity-check matrix using another technique called "Quantum Generator". Using these universal concepts, we implement Quantum Decoders for two different types of linear block codes, namely Hamming codes and Polar codes. Our simple quantum circuits achieve decoding performances comparable with best classical algorithms such as Maximum Likelihood (ML) for Hamming codes and Successive Cancellation (SC) and Successive Cancellation List (SCL) for Polar codes. Using Qiskit, we implemented and compared the decoding performance at different code sizes and noise levels on simulated (both ideal and noisy) quantum computers. Also using Amazon Braket, we verified the algorithm on real quantum computers.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•1 citation

Optimizing the Quantum Circuit for Solving Boolean Equations Based on Grover Search Algorithm

Hui Liu, Fukun Li, Yilin Fan

The solution of nonlinear Boolean equations in a binary field plays a crucial part in cryptanalysis and computational mathematics. To speed up the process of solving Boolean equations is an urgent task that needs to be addressed. In this paper, we propose a method for solving Boolean equations based on the Grover algorithm combined with preprocessing using classical algorithms, optimizing the quantum circuit for solving the equations, and implementing the automatic generation of quantum circuits. The method first converted Boolean equations into Boolean expressions to construct the oracle in the Grover algorithm. The quantum circuit was emulated based on the IBM Qiskit framework and then simulated the Grover algorithm on this basis. Finally, the solution of the Boolean equation was implemented. The experimental results proved the feasibility of using the Grover algorithm to solve nonlinear Boolean equations in a binary field, and the correct answer was successfully found under the conditions that the search space was 221 and three G iterations were used. The method in this paper increases the solving scale and solving speed of Boolean equations and enlarges the application area of the Grover algorithm.

Electronics•Aug 8, 2022•4 citations

Modifications of grover’s quantum algorithm and approaches to their implementation

N.K. Uvarov, А. Д. Хомоненко

Modern variants of Grover›s algorithm and approaches to their implementation are considered. The definition of Grover›s algorithm given, its main three stages are indicated. A generalization of Grover›s algorithm «amplitude amplification» is given. A description of the quantum circuit of Grover›s algorithm is given. An example of a complete Grover quantum circuit for two qubits is considered. The characteristic of quantum search in d-dimensional system with the help of qutrits and qudits is given. Examples of implementation of a number of variants of Grover›s algorithm using IBM Quantum Composer tools are proposed. Descriptions of the latest modifications of Grover›s algorithm are given.

Informatization and communication•Jan 1, 2022•0 citations

Design and Implementation of Encoder/Decoder Quantum Circuits using Decimal to Binary Conversion Method and vice versa

H.M Pooja, M.G Nayana, C. L. Triveni

Quantum Computing is an emerging technology. Quantum Computer will mainly focus on the principles of quantum theory. We design some major data processing circuits like encoder and decoder i.e.,$16\times 4$encoder and$4\times 16$decoder using decimal to binary conversion method and vice versa. Where an encoder is used to encode an incoming signal into an encoded value. A decoder is used in conjugation with the encoder to the decoder, the encoded signals, and recover the original signal. For all the given possible inputs we got probability=1.

IEEE International Conference on Electronics, Computing and Communication Technologies (CONECCT)•Jul 9, 2021•1 citation
Abstract In the coding theory, it is one of the most important research problems to find an efficient algorithm for the decoding process. A quantum computer is an innovative computing device that performs calculations using the principles of quantum mechanics. In this paper, we find a decoding algorithm for binary linear codes using quantum circuits; this is the first time that quantum circuits are used as a main tool for decoding binary linear codes. Our decoding algorithm is mainly based on Grover’s search algorithm. In detail, we study the process of implementing the exhaustive search using quantum circuits for decoding binary linear codes. For our purpose, we design a modified Grover’s algorithm (algorithm 1) using three tools: the matrix multiplier, the Hamming weight counter, and the state indicator. We present algorithm 2, which is a quantum decoding algorithm for binary linear codes. We illustrate algorithm 1 using the [7, 4, 3] Hamming code, and algorithm 2 is implemented by IBM Quantum Composer.
Encoding of finite automata or state machines is critical to modern digital logic design methods for sequential circuits. Encoding is the process of assigning to every state, input value, and output value of a state machine a binary string, which is used to represent that state, input value, or output value in digital logic. Usually, one wishes to choose an encoding that, when the state machine is implemented as a digital logic circuit, will optimize some aspect of that circuit. For instance, one might wish to encode in such a way as to minimize power dissipation or silicon area. For most such optimization objectives, no method to find the exact solution, other than a straightforward exhaustive search, is known. Recent progress towards producing a quantum computer of large enough scale to surpass modern supercomputers has made it increasingly relevant to consider how quantum computers may be used to solve problems of practical interest. A quantum computer using Grover?s well-known search algorithm can perform exhaustive searches that would be impractical on a classical computer, due to the speedup provided by Grover?s algorithm. Therefore, we propose to use Grover?s algorithm to find optimal encodings for finite state machines via exhaustive search. We demonstrate the design of quantum circuits that allow Grover?s algorithm to be used for this purpose. The quantum circuit design methods that we introduce are potentially applicable to other problems as well.
Decoding of linear block codes using syndrome decoding and finding whether there exists a codeword of weightwwwin a set of codewords are known to belong to a class of NP-complete problems. For syndrome decoding of linear block codes, we provide an algorithm that gives a probabilistic solution with least Hamming weight. The algorithm can speed up this process significantly with the help of quantum search algorithm. For this, we make use of a search algorithm inspired from Grover's search. We also suggest a general approach for building a quantum circuit for syndrome detection. We test the algorithm in IBM Quantum Experience using qasm simulator and perform the complexity analysis identifying the algorithm's domain of utility.
Channel Coding is the technique that enables reliable delivery of digital data over unreliable communication channels. For most high performance channel coding techniques, the existing classical algorithms are computationally expensive, making them impractical for throughput-demanding applications with large code sizes. Today’s Noisy Intermediate-Scale Quantum (NISQ) computers, although limited due to a modest number of qubits, short coherence time, and poor gate fidelity, are useful tools for exploring and experimenting with possible solutions to a wide variety of computational problems.In this paper we show how careful initialization of qubits combined with a simple quantum circuit, enables us to perform channel decoding for different linear block codes. We first explain our novel qubit initialization technique which we call "Quantum Soft Decision". We then show how to build a simple quantum circuit based on the Generator or Parity-check matrix using another technique called "Quantum Generator". Using these universal concepts, we implement Quantum Decoders for two different types of linear block codes, namely Hamming codes and Polar codes. Our simple quantum circuits achieve decoding performances comparable with best classical algorithms such as Maximum Likelihood (ML) for Hamming codes and Successive Cancellation (SC) and Successive Cancellation List (SCL) for Polar codes. Using Qiskit, we implemented and compared the decoding performance at different code sizes and noise levels on simulated (both ideal and noisy) quantum computers. Also using Amazon Braket, we verified the algorithm on real quantum computers.
The solution of nonlinear Boolean equations in a binary field plays a crucial part in cryptanalysis and computational mathematics. To speed up the process of solving Boolean equations is an urgent task that needs to be addressed. In this paper, we propose a method for solving Boolean equations based on the Grover algorithm combined with preprocessing using classical algorithms, optimizing the quantum circuit for solving the equations, and implementing the automatic generation of quantum circuits. The method first converted Boolean equations into Boolean expressions to construct the oracle in the Grover algorithm. The quantum circuit was emulated based on the IBM Qiskit framework and then simulated the Grover algorithm on this basis. Finally, the solution of the Boolean equation was implemented. The experimental results proved the feasibility of using the Grover algorithm to solve nonlinear Boolean equations in a binary field, and the correct answer was successfully found under the conditions that the search space was 221 and three G iterations were used. The method in this paper increases the solving scale and solving speed of Boolean equations and enlarges the application area of the Grover algorithm.
Modern variants of Grover›s algorithm and approaches to their implementation are considered. The definition of Grover›s algorithm given, its main three stages are indicated. A generalization of Grover›s algorithm «amplitude amplification» is given. A description of the quantum circuit of Grover›s algorithm is given. An example of a complete Grover quantum circuit for two qubits is considered. The characteristic of quantum search in d-dimensional system with the help of qutrits and qudits is given. Examples of implementation of a number of variants of Grover›s algorithm using IBM Quantum Composer tools are proposed. Descriptions of the latest modifications of Grover›s algorithm are given.
Quantum Computing is an emerging technology. Quantum Computer will mainly focus on the principles of quantum theory. We design some major data processing circuits like encoder and decoder i.e.,16×416\times 416×4encoder and4×164\times 164×16decoder using decimal to binary conversion method and vice versa. Where an encoder is used to encode an incoming signal into an encoded value. A decoder is used in conjugation with the encoder to the decoder, the encoded signals, and recover the original signal. For all the given possible inputs we got probability=1.