Photo By Suzanne William For Unsplash
Finding the shortest path or the most optimised path is prevalent in biological systems. Ants dont just fancy a random rendezvous in search for food. Many biological systems barring humans are quite efficient in the conservation of energy, in carrying out their routines.
A close similarity can be found in the way computers work. The task can be as primitive as searching databases for telephone numbers or breaking cryptographic codes, the algorithms try to complete the task as quickly as possible. In fact, many algorithms, directly or indirectly, have taken inspiration from biological systems.
So, a task in the context of machines, is assessed for speed by counting the steps it takes to end. Computer scientists have always considered that a process takes around N steps because in the worst case, the last item on the list could be the one of interest.
However, Lov Grover, a physicist, showed in 1996, how the strange rules of quantum mechanics allowed the search to be done in a number of steps equal to the square root of N.
A classical (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer.
In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation.
In computational complexity theory, a problem is NP-complete when it can be solved by a restricted class of brute force search algorithms and it can be used to simulate any other problem with a similar algorithm.
More precisely, each input to the problem should be associated with a set of solutions of polynomial length, whose validity can be tested quickly (in polynomial time), such that the output for any input is yes if the solution set is non-empty and no if it is empty.
Amongst all quantum algorithms, the reasons to focus on the Grover search are as follows:
Imagine a phone directory containing N names arranged in a completely random order. In order to find someones phone number with a 50% probability, any classical algorithm (whether deterministic or probabilistic) will need to look at a minimum of N/2 names.
Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names. Grover in his paper proposes that by properly adjusting the phases of various operations, successful computations reinforce each other while others interfere randomly.
As a result, the desired phone number can be obtained in only O(sqrt(N)) steps. Grovers algorithm is within a small constant factor, was considered to be the fastest possible quantum mechanical algorithm back then.
Grovers work was an important factor in preparing for the world of quantum computing, which is still in its infancy.
The first quantum computer capable of implementing it appeared in 1998, but the first scalable version didnt appear until 2017.
Today, a team of researchers from France say they have evidence that Grovers search algorithm is a naturally occurring phenomenon. They claim to have observed this behaviour in electrons.
Grovers search algorithm can be reformulated in a variety of ways. One of these is as a quantum walk across a surfacethe way a quantum particle would move randomly from one point to another.
The team focused on simulating the way a Grover search works for electrons exploring triangular and square grids as shown above.
The objective of this study can be summarized as finding how quickly an electron can find the hole in a grid. And the teams big breakthrough is to show that these simulations reproduce the way real electrons behave in real materials.
The researchers at Universite de Toulon based on their observations, say that free electrons naturally implement the Grover search algorithm when moving across the surface of certain crystals. This has immediate implications for quantum computing. For instance, this can be applied to solve correct the errors in a full-scale quantum computer.
The work also has implications for our thinking about the genetic code and the origin of life. Every living creature on Earth uses the same code, in which DNA stores information using four nucleotide bases. The sequences of nucleotides encode information for constructing proteins from an alphabet of 20 amino acids.
Back in 2000, Apoorva Patel of IISc Bengaluru showed how Grovers algorithm could explain the numbers 4 and 20.
Patel showed that when there are four choices, a quantum search can distinguish between four alternatives in a single step. Indeed, four is optimal number.
However, biologists were dismissive of these results, saying that quantum processes couldnt possibly be at work inside living things.
Now, these latest observations of the French researchers, can fortify two decades old observations of Patel and throw some light on how life itself finds a way.
A century ago, no would have believed that atoms can be manipulated to build computers and the algorithms designed to make these computers better can be used to decode how life springs up.
If this algorithm is really what the researchers say it is then we can safely assume that life is just an example of Grovers algorithm at work !
Read the original paper here.
comments
Original post:
A New Perspective On Grover's Search Algorithm -- Quantum Physics & DNA - Analytics India Magazine
- The application of three-axis low energy spectroscopy in quantum physics research - Phys.Org - May 3rd, 2017 [May 3rd, 2017]
- Physicists breed Schrdinger's cats to find boundaries of the | Cosmos - Cosmos - May 3rd, 2017 [May 3rd, 2017]
- Scientists 'BREED' Schrodinger's Cat in massive quantum physics breakthrough - Express.co.uk - May 3rd, 2017 [May 3rd, 2017]
- Quantum Physics: Are Entangled Particles Connected Via An Undetected Dimension? - Forbes - May 3rd, 2017 [May 3rd, 2017]
- Quantum physics is oppressive - Patheos - Patheos (blog) - June 6th, 2017 [June 6th, 2017]
- It's widely abused as a buzzword. But can quantum mechanics explain how we think? - National Post - June 6th, 2017 [June 6th, 2017]
- Quantum Physics and Love are Super Weird and Confusing, but This Play Makes Sense of Them Both - LA Magazine - June 6th, 2017 [June 6th, 2017]
- One step closer to the quantum internet by distillation - Phys.Org - June 7th, 2017 [June 7th, 2017]
- UW Grad Student from Star Valley Earns Quantum Mechanics Fellowship - SweetwaterNOW.com - June 10th, 2017 [June 10th, 2017]
- Solving systems of linear equations with quantum mechanics - Phys.Org - June 10th, 2017 [June 10th, 2017]
- Quantum Computing Might Be Here Sooner Than You Think ... - Bloomberg - June 14th, 2017 [June 14th, 2017]
- Quantum Physics News - Phys.org - News and Articles on ... - June 14th, 2017 [June 14th, 2017]
- Chinese satellite breaks a quantum physics record, beams entangled photons from space to Earth - Los Angeles Times - June 16th, 2017 [June 16th, 2017]
- Popular Quantum Physics Books - Goodreads - June 16th, 2017 [June 16th, 2017]
- Cybersecurity Attacks Are a Global Threat. Chinese Scientists Have the Answer: Quantum Mechanics - Newsweek - June 17th, 2017 [June 17th, 2017]
- A quantum step to a great wall for encryption - The Hindu - June 18th, 2017 [June 18th, 2017]
- What Is Quantum Mechanics? - livescience.com - June 18th, 2017 [June 18th, 2017]
- Physicists Demonstrate Record Breaking Long-Distance Quantum Entanglement in Space - Futurism - June 20th, 2017 [June 20th, 2017]
- Viewpoint: A Roadmap for a Scalable Topological Quantum Computer - Physics - June 21st, 2017 [June 21st, 2017]
- How Schrdinger's Cat Helps Explain the New Findings About the Quantum Zeno Effect - Futurism - June 21st, 2017 [June 21st, 2017]
- BMW and Volkswagen Try to Beat Apple and Google at Their Own Game - New York Times - June 22nd, 2017 [June 22nd, 2017]
- How quantum physics could revolutionize casinos and betting if you can understand it - Casinopedia - June 22nd, 2017 [June 22nd, 2017]
- Quantum thermometer or optical refrigerator? - Phys.Org - June 22nd, 2017 [June 22nd, 2017]
- Physicists settle debate over how exotic quantum particles form - Phys.Org - June 23rd, 2017 [June 23rd, 2017]
- In 1928, One Physicist Accidentally Predicted Antimatter - Popular Mechanics - June 23rd, 2017 [June 23rd, 2017]
- Atomic imperfections move quantum communication network closer ... - Phys.Org - June 24th, 2017 [June 24th, 2017]
- DOE Launches Chicago Quantum Exchange - HPCwire (blog) - June 26th, 2017 [June 26th, 2017]
- Google to Achieve "Supremacy" in Quantum Computing by the End of 2017 - Big Think - June 26th, 2017 [June 26th, 2017]
- Physicists make quantum leap in understanding life's nanoscale ... - Phys.Org - June 27th, 2017 [June 27th, 2017]
- Berkeley Lab Intern Finds Her Way in Particle Physics - Lawrence Berkeley National Laboratory - June 27th, 2017 [June 27th, 2017]
- Payments Innovation - A Quantum World Of Payments - Finextra (blog) - June 30th, 2017 [June 30th, 2017]
- Why can't quantum theory and relativity get along? - Brantford Expositor - June 30th, 2017 [June 30th, 2017]
- How quantum trickery can scramble cause and effect - Nature.com - June 30th, 2017 [June 30th, 2017]
- Telecommunications, Meet Quantum Physics - Electronics360 - June 30th, 2017 [June 30th, 2017]
- Stephen Colbert Gets a Lesson on Quantum Physics from Brian ... - Patheos (blog) - July 2nd, 2017 [July 2nd, 2017]
- Quantum physics for babies a different bedtime story - CBC.ca - August 24th, 2017 [August 24th, 2017]
- How quantum mechanics can change computing - San Francisco ... - San Francisco Chronicle - August 24th, 2017 [August 24th, 2017]
- Physicists Use Lasers to Set Up First Underwater Quantum Communications Link - Gizmodo - August 24th, 2017 [August 24th, 2017]
- Notable Quotes on Quantum Physics Quantum Enigma - February 15th, 2018 [February 15th, 2018]
- Nothing Is Solid & Everything Is Energy Scientists Explain The World ... - April 11th, 2018 [April 11th, 2018]
- The World Of Quantum Physics: EVERYTHING Is Energy - In5D ... - April 22nd, 2018 [April 22nd, 2018]
- Nothing Is Solid & Everything Is Energy Scientists ... - May 1st, 2018 [May 1st, 2018]
- Black Holes Bolster Case For Quantum Physics' Spooky Action ... - August 29th, 2018 [August 29th, 2018]
- Physics4Kids.com: Modern Physics: Quantum Mechanics - September 29th, 2018 [September 29th, 2018]
- Quantum Theory - Full Documentary HD - November 6th, 2018 [November 6th, 2018]
- Quantum mind - Wikipedia - February 6th, 2019 [February 6th, 2019]
- What is quantum theory? - Definition from WhatIs.com - May 5th, 2019 [May 5th, 2019]
- The Ultimate Mystery? Consciousness May Exist in the Absence of Matter (Weekend Feature) - The Daily Galaxy --Great Discoveries Channel - September 19th, 2019 [September 19th, 2019]
- Faculty Opening, Quantum Information and Condensed Matter Experiment - Physics - September 19th, 2019 [September 19th, 2019]
- Become the physicists the world needs with the help of a physics degree - Study International News - September 19th, 2019 [September 19th, 2019]
- Imec and NUS working on chip-based quantum cryptography - Optics.org - September 19th, 2019 [September 19th, 2019]
- Strong LightMatter Coupling in Molecular and Material Engineering - Advanced Science News - September 19th, 2019 [September 19th, 2019]
- The key to bigger quantum computers could be to build them like Legos - MIT Technology Review - September 19th, 2019 [September 19th, 2019]
- Australian universities are accused of trading free speech for cash - The Economist - September 19th, 2019 [September 19th, 2019]
- APS Physics Career Center - Physics - September 19th, 2019 [September 19th, 2019]
- Assistant Professor of Physics, Employment - Physics - September 19th, 2019 [September 19th, 2019]
- A new approach to quantum gravity - Tech Explorist - September 19th, 2019 [September 19th, 2019]
- A Huge Experiment Has 'Weighed' the Tiny Neutrino, a Particle That Passes Right Through Matter - Gizmodo - September 19th, 2019 [September 19th, 2019]
- Many Worlds, But Too Much Metaphor - Forbes - September 19th, 2019 [September 19th, 2019]
- Iran to open 1st quantum physics lab in a year: AEOI head - Mehr News Agency - English Version - September 19th, 2019 [September 19th, 2019]
- Quantum Computing Breakthrough: New Detection Tool Uncovers Noise That Can Kill Qubits - SciTechDaily - September 19th, 2019 [September 19th, 2019]
- A quantum computing startup that spun out of a Harvard lab just came out of stealth mode with $2.7 million in seed funding from investors like Samsung... - September 19th, 2019 [September 19th, 2019]
- Important Quantum Algorithm May Be a Property of Nature - Technology Networks - September 19th, 2019 [September 19th, 2019]
- Iran to open first quantum physics lab in a year: AEOI head - Quantaneo, the Quantum Computing Source - September 19th, 2019 [September 19th, 2019]
- Sean Carroll: Universe a 'tiny sliver' of all there is - PBS NewsHour - September 19th, 2019 [September 19th, 2019]
- IBM cuts ribbon on quantum computing centre wherein a 53-qubit monster lurks - The Register - September 19th, 2019 [September 19th, 2019]
- In 'Something Deeply Hidden,' Sean Carroll Argues There Are Infinite Copies Of You - NPR - September 19th, 2019 [September 19th, 2019]
- Physicists race to develop room-temperature quantum chips - The Next Web - September 19th, 2019 [September 19th, 2019]
- This One Experiment Reveals More About Reality Than Any Quantum Interpretation Ever Will - Forbes - September 19th, 2019 [September 19th, 2019]
- Our world is in need of the Mahatmas teachings: Dalai Lama - Livemint - October 2nd, 2019 [October 2nd, 2019]
- Quantum-inspired Beckman Institute celebration will be anything but small - Central Illinois Buzz - October 2nd, 2019 [October 2nd, 2019]
- Is It a Wave or a Particle? It's Both, Sort Of. - Space.com - October 2nd, 2019 [October 2nd, 2019]
- Princeton announces initiative to propel innovations in quantum science and technology - Quantaneo, the Quantum Computing Source - October 2nd, 2019 [October 2nd, 2019]
- Precision physics with 'tabletop' experiments - Stanford University News - October 2nd, 2019 [October 2nd, 2019]
- Andrea Young uncovers the strange physics of 2-D materials - Science News - October 2nd, 2019 [October 2nd, 2019]
- A Scientific Explainer of What Terrence Howard Was Talking About at the Emmys - VICE - October 2nd, 2019 [October 2nd, 2019]
- China's Silicon Valley aims to become the country's top research center - Abacus - October 16th, 2019 [October 16th, 2019]
- New Quantum-Mechanical Dissipation Mechanism Observed for the First Time - SciTechDaily - October 16th, 2019 [October 16th, 2019]
- Physicists have found quasiparticles that mimic hypothetical dark matter axions - Science News - October 16th, 2019 [October 16th, 2019]
- The Power of Wrong Answers in Science Education - WIRED - October 16th, 2019 [October 16th, 2019]