Quantum Algorithm

Article Info

Contributed by
2 authors

Last updated on
2022-02-18 03:01:24

Improve this article

Variational Quantum Algorithm
Quantum Computation Language
Shor's Algorithm
Grover's Algorithm
Quantum Walk
Quantum Simulation

Article Versions

9 2022-02-18 03:01:24
3411,3409 9,3411

By arvindpdmn

Updated See Also. Publishing.
8 2022-02-17 06:23:12
3409,3298 8,3409

By techlady

Edited
7 2022-02-14 13:19:00
3298,3297 7,3298

By techlady

Edited
6 2022-02-14 13:16:35
3297,3252 6,3297

By techlady

Working on Editing
5 2022-02-03 12:22:01
3252,3238 5,3252

By techlady

Edited

Chat Room

Submitting ...

You are editing an existing chat message.
2022-02-17 03:50:13
-

By arvindpdmn

1. I mentioned "Wikipedia, Contributors" as an example. Similar problems are there in some other refs.
2. QA design: lot of emphasis on Yao. Is this the only one?
3. Please remove bold style where it has been used for sentences or parts of it. Bold for some headings in answers is okay. Bold for "Shor's Algorithm" where it is first explained is okay.
4. Last question doesn't add any value. It's same as first question.
5. "as it a combination quantum state preparation": grammar mistake.
6. VQA: second para doesn't read well after the first para. Last sentence repeats what's in the first para. Entire answer should read well. New authors have this problem since they may copy and paste from different sources.
2022-02-14 13:18:40
-

By techlady

Hi Sir,
I couldn't find relevant information about "algo complexity comparison between classical and qu algo".

Rest suggestions have been taken care of in the best way possible from my side.

Thank you.
2022-02-14 03:42:59
-

By arvindpdmn

1. Citations: incorrectly done for image captions: please study the changes I made for the Qubit article and correct.
2. Entire paragraphs are bolded. Not recommended. This is rarely done in professional publications. At most a short phrase should be bolded to draw the reader's attention.
3. Original proposal had these three questions and would like to see them addressed: (a) How are quantum algorithms different from classical algorithms? (b) What are the unique properties of quantum algorithms? (c) How can quantum algorithms solve dynamic programming problems? I think at least (a) and (b) can be combined addressed in one question. (c) also looks useful.
4. VQA: same comment as previous review: no explanation about what is VQA and how it's different from QA. The first para is fine since it sets the context by mentioning current problems with QA. Also, "Hybrid quantum/classical algorithms": isn't VQA an example of this? Answer can be improved by understanding better.
5. "Wikipedia, Contributors. 2004. "Quantum algorithm." Wikipedia, the free encyclopedia. Accessed 2022-01-18." Not the correct way to format the reference. See this article to get an idea how it should be corrected: https://devopedia.org/quantum-computing
6. Need algo complexity comparison between classical and qu algo.
2022-02-02 14:20:23
-

By arvindpdmn

1. Your proposal had more questions. Article seems too short for such a topic.
2. Summary and first answer overlap/repetitive. First answer can be removed.
3. Montanaro paper is duplicated: essentially the same paper from two sites.
4. Important: include QA Zoo as a source: https://quantumalgorithmzoo.org/
5. Classification into three categories is not convincing. Montanaro and Zoo are two good sources to improve this. However, your answer may be correct. Please share the exact source where I can verify mention of these three classes.
6. Identifying the class is a good approach. Since there are dozens of algos, this article should give a bird's eye view.
7. Why do we need? Should be the first question.
8. VQA: answer needs lot of improvement. A lot is written about why VQA but very little info about what is VQA.
9. Didn't do detailed review of milestones but looks good. Bold some words to focus the reader's attention. For example, for first milestone bold **Deutsch–Jozsa algorithm**.
10. Need algo complexity comparison between classical and qu algo.
11. "Contributors, Wikipedia": not the correct format or attribution of Wikipedia page. See examples from other articles.
12. https://www.researchgate.net/publication/220696169_Quantum_Computer_Science : not correct to give ResearchGate as the site or publisher: follow DOI to get the correct way to cite this, URL can be ResearchGate.
13. Sources for further research:
- https://arxiv.org/abs/1804.03719
- https://arxiv.org/aba/2109.06493
- https://quantum-journal.org/papers/q-2020-10-11-341/
- https://arxiv.org/ftp/arxiv/papers/2010/2010.15559.pdf (sec. 2.2), algo characteristics in sec. 3
2022-01-31 16:07:35
-

By techlady

Yes, Sir

Quantum Application. Source: ScienceDirect 2021.

A quantum computer is a machine that employs quantum mechanics to perform tasks that would be quite challenging for a machine based solely on classical physics laws to accomplish. Quantum computing's future applications include everything from cracking cryptographic systems to developing novel treatments. These applications are based on quantum algorithms, which run on a quantum computer and achieve a speedup or other efficiency advantage over any other classical method.

Quantum computers use quantum algorithms to outperform traditional computers. Cryptography, search and optimization, quantum system modelling, and solving huge systems of linear equations are all areas where quantum methods can be used.

Shor's algorithm for factoring and Grover's algorithm for searching an unstructured database or an unordered list are two of the most popular search methods. Shor's algorithms are faster (probably more powerful) than the well-known traditional factoring algorithm, the general number field sieve.

Discussion

Why do we need Quantum Algorithm?
Quantum Algorithm: Applications. Source: ResearchGate 2021.
To do factoring, the well-known quantum algorithm is Shor's Algorithm. This method of quantum factoring takes about the same amount of time to function as a whole number of digits, while the older advanced algorithm takes about the exposure time. The notion that complex factoring is critical to functioning of modern cryptosystems, allows for most e-commerce. In these cryptosystems, the user can encrypt information and "eavesdroppers" can only determine the information by entering a large number. This strategy is useful for keeping information confidential as long as there are no quick fixes.
Modeling of chemical and physical interactions is the another known quantum computer program. Because the amount of space required to track a quantum system increases rapidly with the number of particles, quantum mechanics are often difficult to duplicate using a standard computer. This has made understanding of the operation of many important systems and interactions, from advanced superconductors to photosynthesis, difficult for scientists and engineers. Quantum computers, for example, are expected to improve and accelerate drug research and industrial chemical processes by allowing 'in silico'(an experiment that is performed on computer) of chemical compounds and performance.
What are the Characteristics of a Quantum Algorithm?
Quantum computing techniques can be accomplished using classical computer infrastructure by applying quantum algorithms. It is critical to analyze and categorise quantum computing technologies using quantum algorithms to describe characteristics. Parallelism, aggregate count of accessible qubits, topologies, algorithms for locating qubits, and qubit operations are all algorithmic aspects of quantum computing technology.
Because parallel implementation of quantum gates is essential to either prevent or decrease qubit decoherence, parallelism is a key characteristic. Another characteristic that contributes to the quantum computer's stability and scalability is the total number of qubits available. The topologies of a quantum computer's architecture are the multiple conceivable groupings of distinct physical devices.
The fundamental objective is architecture optimization, which allows for a seamless flow of data and information among the many physical parts of the system. The addressing mechanism for identifying a single qubit is quite complicated logically. This capability allows for a more detailed examination of qubit states in terms of quantum computer physical implementation. Moreover, in order to conduct any operation on qubits, they must be transported from the address where they are stored to the place where the qubit gates are acting on them.
How can the Quantum Algorithms be classified?
Quantum Fourier Transform-based algorithms:
Quantum Fourier transform is a quantum version of the discrete Fourier transform that is utilised in a variety of quantum techniques. In the field F2, the Hadamard transform is an example of a quantum Fourier transform over an n-dimensional vector space. Only a polynomial number of quantum gates are required to accomplish the quantum Fourier transform on a quantum computer.
Amplitude Amplification-based algorithms:
Amplitude amplification is a method that enables a quantum state's subdomain to be amplified. It frequently results in quadratic speedups when compared to traditional techniques. That can be regarded as a generalisation of Grover's algorithm.
Quantum Walk-based algorithms:
Quantum walks are a powerful and general framework for creating rapid quantum algorithms. A quantum walk is based on the simulated coherent quantum evolution of a particle moving on a graph, similar to how a random walk method is based on the simulated motion of a particle moving randomly within some underlying graph structure.
Hybrid quantum/classical algorithms:
They are predicted to be the first useful applications for quantum computing, as they are well-suited for execution on NISQ (noisy intermediate-scale quantum) devices by integrating quantum computers with classical computers.
What is a Variational Quantum Algorithm?
Variational Quantum Algorithm. Source: Nature 2022.
Variational Quantum Algorithm(VQA) is a Hybrid type of algorithm, as it is a combination quantum state preparation and measurement with classical optimization. This methodology can be used to locate low-energy eigenstates as well as to minimise any objective function.
The variational method is a classical method for obtaining low energy states of a quantum system in quantum theory. The basic idea behind this method is to build a trial wave function (also known as an ansatz) as a function of some parameters, and then determine the values of these parameters that minimise the energy's expectation value in relation to these parameters. The expectation value serves as an upper bound on the energy of the ground state, and the reduced ansatz is an approximation to the lowest energy eigenstate. As a result, a new type of algorithm called as Variational Quantum Algorithm(VQA) has emerged.
How can a Quantum Algorithm be designed?
Yao is a quantum computation research software that solves real-world challenges. Given the limits of noisy intermediate-scale quantum circuits in the near term, treating quantum devices as co-processors and enhancing their capabilities with classical computing resources is useful. VQAs have emerged as a potential study field. A quantum circuit with configurable gate parameters and a classical optimizer are frequently used in these techniques.
For designing and testing quantum algorithms in these difficult domains, efficient quantum software is critical. Yao is an open-source framework for designing quantum algorithms with exceptional extensibility and efficiency. Quantum circuits can be programmed in a general and differentiable way with Yao. It simulates tiny to intermediate-sized quantum circuits with state-of-the-art performance that is important to near-term applications.
The quantum block intermediate representation of quantum circuits, a built-in automated differentiation engine tuned for reversible computing, and batched quantum registers with GPU(graphics processing unit) acceleration are among the design principles and critical methodologies underpinning Yao.
Besides increasing the number of qubits in experiments, further research objectives ask for quantum software with a low overhead for repetitive feedback control, convenient circuit structure modifications, and rapid gradient calculation.
How can Quantum Algorithms solve Dynamic Programming Problems?
Quantum algorithms can be used to solve dynamic programming issues with finite and infinite horizons. For the similar jobs, the query complexity lower bounds for classical randomised algorithms are examined, and a polynomial separation between the query complexity of quantum algorithms and the best-case query complexity of conventional randomised algorithms can be demonstrated as a result. Quantum algorithms can provide a quadratic advantage in terms of the number of states and actions in the dynamic programming problem up to polylogarithmic factors. However, the speedup achieved comes at the expense of the introduction of other polynomial factors in the scaling of the algorithm, which contribute to the solution's precision. The quantum algorithm framework is concerned with discrete and combinatorial optimization issues that have traditionally been tackled with dynamic programming techniques.

Milestones

1992

The Deutsch–Jozsa algorithm is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. This is perhaps the earliest result in the computational complexity of quantum computers, proving that they were capable of performing some well-defined computational task more efficiently than any classical computer.

1994

Peter Shor of Bell Laboratories develops a quantum algorithm for factoring integers that has the potential to decrypt RSA-encrypted communications, a widely-used method for securing data transmissions. Isaac Chuang and Yoshihisa Yamamoto propose a quantum-optical realization of a quantum computer to implement Deutsch's algorithm. Their work introduces dual-rail encoding for photonic qubits.

1996

Lov Grover of Bell Laboratories invents the quantum database search algorithm. The quadratic speedup is not as dramatic as the speedup for factoring, discrete logs, or physics simulations. However, the algorithm can be applied to a much wider variety of problems. Any problem that has to be solved by random, brute-force search, can take advantage of this quadratic speedup (in the number of search queries).

1998

First experimental demonstration of a quantum algorithm. A working 2-qubit NMR quantum computer is used to solve Deutsch's problem by Jonathan A. Jones and Michele Mosca at Oxford University and shortly after by Isaac L. Chuang at IBM's Almaden Research Center and Mark Kubinec and the University of California, Berkeley together with coworkers at Stanford University and MIT.[Contributors 2005] First execution of Grover's algorithm on an NMR computer. Hidetoshi Nishimori & colleagues from Tokyo Institute of Technology showed that quantum annealing algorithm can perform better than classical simulated annealing.

2003

Implementation of the Deutsch–Jozsa algorithm on an ion-trap quantum computer at the University of Innsbruck.

2007

First use of Deutsch's Algorithm in a cluster state quantum computer.

2009

Quantum algorithm developed for differential equation systems.

2013

First resource analysis of a large-scale quantum algorithm using explicit fault-tolerant, error-correction protocols was developed for factoring.

2016

Physicists led by Rainer Blatt joined forces with scientists at MIT, led by Isaac Chuang, to efficiently implement Shor's algorithm in an ion-trap based quantum computer.

References

Article Stats

1578

Words

Authors

Edits

Chats

Likes

4875

Hits

Cite As

Devopedia. 2022. "Quantum Algorithm." Version 9, February 18. Accessed 2024-06-25. https://devopedia.org/quantum-algorithm

Contributed by
2 authors

Last updated on
2022-02-18 03:01:24

Improve this article

algorithms information theory classification summarization quantum computing quantum mechanics

Variational Quantum Algorithm
Quantum Computation Language
Shor's Algorithm
Grover's Algorithm
Quantum Walk
Quantum Simulation

Quantum Algorithm

Discussion

Milestones

References

Further Reading

Article Stats

Author-wise Stats for Article Edits

Cite As

See Also

Article Warnings

Login