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
Real Time with…. IPC APEX EXPO 2024: Innovation and Collaboration at EPTAC
05/06/2024 | Real Time with...IPC APEX EXPOGuest Editor Kelly Dack and EPTAC Vice President Leo Lambert discuss the partnership between EPTAC and Blackfox, their program alignment, and future expansion plans. Leo introduces Burak Gokmen as the new "leader of the pack." The focus then shifts to Nano Dimensions' 3D printed circuit boards, emphasizing the need for proper documentation and training.
The New Industry: Will the Growth Continue?
04/30/2024 | I-Connect007 Editorial TeamHow sustainable are the primary financial models in the United States regarding PCB fabrication shops? In this interview with economic experts Shawn DuBravac and Tom Kastner, we explore what’s happening with U.S. printed circuit board shops in today’s market, how consolidation affects the industry, and what can be done.
Taiyo Circuit Automation Installs New DP3500 into Fuba Printed Circuits, Tunisia
04/25/2024 | Taiyo Circuit AutomationTaiyo Circuit Automation is proud to be partnered with Fuba Printed Circuits, Tunisia part of the OneTech Group of companies, a leading printed circuit board manufacturer based out of Bizerte, Tunisia, on their first installation of Taiyo Circuit Automation DP3500 coater.
Determining the Value-add of Box Build
04/24/2024 | Nolan Johnson, I-Connect007At a strategic level, adding box-building services makes sense for customer loyalty. But is it really that simple? Jon Schmitz, who manages customer engagement at RiverSide Integrated Solutions, talk about about what it really takes to be successful in offering EMS and final assembly services under the same company banner.
Designer’s Notebook: What Designers Need to Know About Manufacturing, Part 2
04/24/2024 | Vern Solberg -- Column: Designer's NotebookThe printed circuit board (PCB) is the primary base element for providing the interconnect platform for mounting and electrically joining electronic components. When assessing PCB design complexity, first consider the component area and board area ratio. If the surface area for the component interface is restricted, it may justify adopting multilayer or multilayer sequential buildup (SBU) PCB fabrication to enable a more efficient sub-surface circuit interconnect.