Classical Computers Have a Hard Time Understanding 'Quantum Accents'
October 31, 2018 | University of California - BerkeleyEstimated reading time: 5 minutes
Vazirani's team referred to an analogy between the output of the random quantum circuit and a string of random syllables in English: even if the syllables don't form coherent sentences or words, they will still possess an English "accent" and will be recognizably different from Greek or Sanskrit.
They showed that producing a random output with a "quantum accent" is indeed hard for a classical computer through a technical complexity theoretic construct called "worst-to-average-case reduction."
The next step was to verify that a quantum device was actually speaking with a quantum accent. This relies on the Goldilocks principle -- a 50-qubit machine is large enough to be powerful, but small enough to be simulated by a classical supercomputer. If it's possible to verify that a 50-qubit machine speaks with a quantum accent, then that would provide strong evidence that a 100-qubit machine, which would be prohibitively hard to simulate classically, would do so, as well.
But even if a classical supercomputer were programmed to speak with a quantum accent, would it be able to recognize a native speaker? The only way to verify the output of the speaker is by a statistical test, said the Berkeley researchers. Google researchers are proposing to measure the degree of matching by a metric called "cross-entropy difference." A cross-entropy score of 1 would be an ideal match.
The alleged quantum device may be regarded as behaving like an ideal quantum circuit with random noise added. Fefferman and Bouland say the cross-entropy score will certify the authenticity of the quantum accent provided the noise always adds entropy to the output. This is not always the case - for example if the noise process preferentially erases 0s over 1s, it can actually reduce the entropy.
"If Google's random circuits are generated by a process that allows such erasures, then the cross-entropy would not be a valid measure of quantum supremacy," said Bouland. "That's partly why it will be very important for Google to pin down how its device deviates from a real random quantum circuit."
These results are an echo of work that Vazirani did in 1993 with his student Ethan Bernstein when they presented the first formal evidence that quantum computers would exponentially speed up certain computations. This opened the door to quantum algorithms by showing that quantum computers violate the Extended Church-Turing thesis, a foundational principle in computer science.
Peter Shor of Bell Labs took their work one step further by showing that a very important practical problem, integer factorization, could be exponentially sped up by a quantum computer.
"This sequence provides a template for the race to build working quantum computers," said Vazirani. "Quantum supremacy is an experimental violation of the Extended Church-Turing thesis. Once that is achieved, the next challenge will be to design quantum computers that can solve practically useful problems."
Page 2 of 2Suggested Items
PCB Market Size to Grow by $29.06B from 2024-2028
05/17/2024 | PRNewswireThe global printed circuit board (PCB) market size is estimated to grow by USD 29.06 bn from 2024-2028, according to Technavio. The market is estimated to grow at a CAGR of over 6.6% during the forecast period.
Taiflex Announces Grand Opening of Thailand Factory
05/17/2024 | TAIFLEX Scientific Co. LtdTaiflex Scientific Co., Ltd., a global leader in advanced flexible printed circuit (FPC) materials, held the grand opening ceremony of its Thailand factory at the Amata City Chonburi Industrial Estate in Chonburi, Thailand.
Listen Up: Popular Podcast Series Returns With Discussion of Electroless Copper
05/16/2024 | I-Connect007In the latest episode of the podcast series, On the Line With: Designing for Reality, Nolan Johnson returns to Sunstone Circuits in Mulino, OR, to continue down the manufacturing process with Matt Stevenson.
IDENTCO Highlights Automation Capabilities and PCB Labeling at PCB East
05/13/2024 | IDENTCOIDENTCO – a manufacturer of high-performance labeling solutions for the power equipment, electronics, transportation, and general industrial sector – will highlight its automation capabilities and PCB labeling solutions at PCB East, June 4-7 in Boxborough, MA, Booth #301.
Podcast Review: On the Line with… Designing for Reality
05/09/2024 | Duane Benson, Positive Edge LLCAs a technologist, if I were forced to come up with just one recurring theme that I might call a professional “nemesis,” it would be the difference between theory and reality. A lot of technology we have at our disposal works well in theory but falls short when reality hits. That’s not the only reason I chose to listen to and review On the Line with… Designing for Reality, featuring a series of conversations with ASC Sunstone’s Matt Stevenson, but it certainly helped that the title caught my eye.