Related Experiment Video
Updated: Jul 26, 2026
06:42
Generation and Coherent Control of Pulsed Quantum Frequency Combs
Published on: June 8, 2018
Demonstration of Shor's factoring algorithm for N [Formula: see text] 21 on IBM quantum processors
1Department of Physics, Stellenbosch University, Matieland, 7602 South Africa.
Scientific Reports
|August 17, 2021
Summary
Researchers demonstrate a quantum order-finding algorithm for factoring 21 using approximate Toffoli gates on IBM quantum processors. This proof-of-concept shows entanglement and offers techniques for larger quantum factoring tasks.
Area of Science:
- Quantum Computing
- Number Theory
- Quantum Algorithms
Background:
- Integer factorization is a computationally hard problem crucial for cryptography.
- Quantum algorithms, like Shor's algorithm, offer potential speedups for factorization.
- Previous demonstrations of quantum factoring have limitations in gate implementation and scale.
Purpose of the Study:
- To demonstrate a proof-of-concept for a quantum order-finding algorithm to factor the integer 21.
- To explore the use of approximate Toffoli gates with residual phase shifts for improved efficiency and correctness.
- To implement and verify the algorithm on a small-scale quantum processor, confirming key quantum phenomena.
Main Methods:
- Utilized a compiled quantum phase estimation routine.
- Employed a novel configuration of approximate Toffoli gates with residual phase shifts.
- Implemented the algorithm on IBM quantum processors using five qubits.
Main Results:
- Successfully factored the integer 21.
- Verified the presence of entanglement between control and work register qubits.
- Achieved functional correctness with the approximate Toffoli gate configuration.
Conclusions:
- The demonstrated techniques are viable for small-scale quantum factoring.
- The use of approximate Toffoli gates preserves functional correctness and may enable larger factoring tasks.
- This work provides insights for implementing quantum algorithms on limited, noisy qubit systems.
Related Concept Videos
01:28Rational Expressions
Rational expressions are algebraic fractions in which both the numerator and the denominator are polynomials. These expressions follow the arithmetic rules of numerical fractions but require extra care due to the presence of variables. A fundamental part of working with rational expressions is identifying values that make the expression undefined, typically those that result in division by zero or undefined radicals.Determining the DomainThe domain of a rational expression includes all real...
01:26Long Division of Polynomials
Polynomial division is an essential algebraic process to simplify expressions and solve equations. Just as numerical division separates a number into quotient and remainder, polynomial long division partitions a polynomial into simpler components; in this context, the dividend is the polynomial being divided, the divisor is the expression dividing it, and the result is expressed in terms of a quotient and a remainder.The division begins by arranging the dividend and divisor in standard...
01:30The Binomial Theorem
The Binomial Theorem is a foundational principle in algebra used to expand expressions raised to a power. It provides a structured approach for expanding binomials of the form (a+b)n, where a and b are variables or constants representing algebraic expressions, and n is a non-negative integer.The general form of the Binomial Theorem is:Each term in the expansion involves a binomial coefficient, which is calculated using factorials:The exponent of a in each term decreases from n to 0, while the...
01:28Synthetic Disvision of Polynomials
Synthetic division is an efficient algorithmic approach for dividing a polynomial by a linear binomial of the form x - c, where c is a real number. This method is helpful due to its streamlined process, which avoids the more cumbersome steps involved in the traditional long division of polynomials. It simplifies computation and serves as a practical tool for evaluating polynomials and identifying their factors.To perform synthetic division, one begins by listing the coefficients of the...
01:29Rationalizing Substitutions
Integrals involving non-rational functions are often difficult to evaluate using standard techniques, especially when radicals appear in the integrand. Rationalizing substitution provides a systematic method for simplifying such integrals by converting them into rational forms that are easier to handle.Consider a rod whose linear mass density depends on a constant linear density, a characteristic length, and the distance from the left end of the rod. Determining the total mass requires...
01:30Binomial Expansion Using Pascal's Triangle
Expanding a binomial expression such as (a + b)n results in a predictable sequence of terms that can be systematically derived using Pascal’s Triangle. This triangular array of numbers plays a central role in understanding and computing the coefficients of binomial expansions.Pascal’s Triangle is constructed such that each row corresponds to the coefficients of a binomial raised to a power. The topmost row, known as the zeroth row, corresponds to (a + b)0, and each successive row gives the...