0 Persons are tagged with #quantumcomputing

#quantumcomputing

waynerad@diasp.org
Wayne Radinsky

"For those who don't yet know from their other social media: a week ago the cryptographer Yilei Chen posted a preprint, eprint.iacr.org/2024/555, claiming to give a polynomial-time quantum algorithm to solve lattice problems. For example, it claims to solve the GapSVP problem, which asks to approximate the length of the shortest nonzero vector in a given n-dimensional lattice, to within an approximation ratio of ~n4.5. The best approximation ratio previously known to be achievable in classical or quantum polynomial time was exponential in n."

"If it's correct, this is an extremely big deal. It doesn't quite break the main lattice-based cryptosystems, but it would put those cryptosystems into a precarious position, vulnerable to a mere further polynomial improvement in the approximation factor. And, as we learned from the recent NIST competition, if the lattice-based and LWE-based systems were to fall, then we really don't have many great candidates left for post-quantum public-key cryptography! On top of that, a full quantum break of LWE (which, again, Chen is not claiming) would lay waste (in a world with scalable QCs, of course) to a large fraction of the beautiful sandcastles that classical and quantum cryptographers have built up over the last couple decades--everything from Fully Homomorphic Encryption schemes, to Mahadev's protocol for proving the output of any quantum computation to a classical skeptic."

Wow, that's quite a lot. Let's see if we can figure out what's going on here.

First of all, I hadn't heard of these "lattice" problems, but doing some digging, I found they've been of great interest to people working on quantum computers, because they're thought to be resistant to attacks from quantum computers. Quantum computers have this magical ability to use the superposition of wavefunctions to test "all combinations at once" for a mathematical problem, which could be finding a key that decrypts an encrypted message. This magical ability is harder to tap into than it sounds because, first of all, you need enough qubits (quantum bits -- the superposition bits that quantum computers use instead of the regular 0 or 1 bits of regular computers), and that's really hard because all the qubits have to be entangled, and maintaining a boatload of entangled qubits usually involves freezing atoms to near absolute zero and other such difficult things. And second of all, you have to find an algorithm -- quantum computers are not straightforward to program, and can only "run" "programs" written specifically for quantum computers, with algorithms that have been invented to solve a particular mathematical problem using quantum physics.

What supposedly makes "lattice" problems harder to solve than RSA, Elliptic Curve Cryptography, and so on, is that with lattices, you can have any number of dimensions. This increase in dimensionality cranks up the number of qubits required much faster than traditional algorithms such as RSA, Elliptic Curve Cryptography, and so on. So they stand a much better chance of outpacing the advancement of quantum computers. Also, nobody has ever come up with an algorithm for cracking lattice problems...

...until now, maybe. That's what this post is about. Possibly this Yilei Chen cryptographer has found an algorithm. The specific encryption algorithm that he may have found a way to crack with a quantum computer algorithm is called GapSVP. SVP stands for "shortest vector problem" and clicking through on the link will take you to a Wikipedia page that explains the mathematics behind it. However if you scroll down in the original post you'll see there is discussion of a bug in cryptographer Yilei Chen's algorithm. It is not known whether the algorithm can be fixed or whether this means GapSVP and LWE remain unbroken.

Speaking of LWE, the post also mentions LWE without giving a clue what "LWE" means. LWE stands for "Learning With Errors". In fact if you clicked through on GapSVP to the Wikipedia page, you can find a handy link to the Learning With Errors page at the bottom in the "See also" section. With LWE, you have an n-dimensional "ring" of integers -- called a "ring" instead of a "vector" because they are all modulo some prime number (remember we make this hard by making the number of dimensions and the size of the prime number huge) -- which you run through some secret linear transformation function and then perturb with some error, perhaps drawn from a Gaussian distribution. To crack the system you have to recover the secret linear transformation function. Mathematicians have proven LWE is equivalent to lattice problems and therefore is a lattice problem.

The mention of Mahadev's protocol, which you can find out all about by clicking through on that link, refers to a method of verifying that a quantum algorithm works using a classical computer. The protocol works by forcing the qubits into states that are predetermined ahead of time, and then verifying those states are achieved. Of course a classical computer cannot verify the output of a quantum computer for any given input.

That IACR preprint

#solidstatelife #cryptography #quantumcomputing

Quantum Algorithms for Lattice Problems

We show a polynomial time quantum algorithm for solving the learning with errors problem (LWE) with certain polynomial modulus-noise ratios. Combining with the reductions from lattice problems to LWE shown by Regev [J.ACM 2009], we obtain...

6 Likes
1 Shares
2 Likes
1 Shares
danie10@squeet.me
Danie

Steve Gibson’s explanation of the quantum computing breakthrough

Security Now logo
I’ve not really bothered to follow the quantum computing hype until it was going to become any sort of reality in our future. The issue has been mostly around its instability and required error correction.

Some encryption has already been pronounced as quantum safe, e.g. Signal’s, but again we’d have to see that to believe it.

What has dramatically changed now, is that instead of the unstable physical quantum bits (qubits), a Harvard team has come up with a way to work with logical qubits s formed from bundles of redundant, error-corrected physical qubits. These can store information for use in a quantum algorithm. Creating logical qubits as controllable units — like classical bits — has been a fundamental obstacle for the field, and it’s generally accepted that until quantum computers can run reliably on logical qubits, the technology cannot really take off.

So, Steve does explain this in a way which is a bit easier to understand that it has taken things forward quite a bit. The link below is to the video of this episode of Security Now where he explains it. There is also a link on that page though to the PDF with the text notes from the show if you prefer to scan the text.

See https://twit.tv/shows/security-now/episodes/952?autostart=false
#Blog, #quantumcomputing, #technology

3 Likes
waynerad@diasp.org
Wayne Radinsky

"China's global lead extends to 37 out of 44 technologies that the Australian Strategic Policy Institute (ASPI) is now tracking, covering a range of crucial technology fields spanning defence, space, robotics, energy, the environment, biotechnology, artificial intelligence (AI), advanced materials and key quantum technology areas. The Critical Technology Tracker shows that, for some technologies, all of the world's top 10 leading research institutions are based in China and are collectively generating nine times more high-impact research papers than the second-ranked country (most often the US). Notably, the Chinese Academy of Sciences ranks highly (and often first or second) across many of the 44 technologies included in the Critical Technology Tracker. We also see China's efforts being bolstered through talent and knowledge import: one-fifth of its high-impact papers are being authored by researchers with postgraduate training in a Five-Eyes country. China's lead is the product of deliberate design and long-term policy planning, as repeatedly outlined by Xi Jinping and his predecessors."

"A key area in which China excels is defence and space-related technologies. China's strides in nuclear-capable hypersonic missiles reportedly took US intelligence by surprise in August 2021."

"Over the past five years, China generated 48.49% of the world's high-impact research papers into advanced aircraft engines, including hypersonics, and it hosts seven of the world's top 10 research institutions in this topic area."

"China has built the foundations to position itself as the world's leading science and technology superpower, by establishing a sometimes stunning lead in high-impact research across the majority of critical and emerging technology domains."

"The US comes second in the majority of the 44 technologies examined in the Critical Technology Tracker. The US currently leads in areas such as high performance computing, quantum computing and vaccines. Our dataset reveals that there's a large gap between China and the US, as the leading two countries, and everyone else. The data then indicates a small, second-tier group of countries led by India and the UK: other countries that regularly appear in this group -- in many technological fields -- include South Korea, Germany, Australia, Italy, and less often, Japan."

You can compare any technologies between countries. The technologies are categorized into "Sensing, timing and navigation", "Transportation, robotics and space", "Artificial intelligence, computing and communications", "Energy and environment", "Advanced materials & manufacturing", "Biotechnology, gene technologies and vaccines", and "Quantum".

In the "Sensing, timing and navigation" category, they have "Photonic sensors".

In the "Transportation, robotics and space" category, they have "Photonic sensors", "Space launch systems", "Small satellites", "Drones, swarming and collaborative robots", "Autonomous systems operation technology", "Advanced robotics", and "Advanced aircraft engines".

In the "Artificial intelligence, computing and communications" category, they have "Artificial intelligence algorithms and hardware accelerators", "Advanced data analytics", "Advanced radiofrequency communications", "Advanced optical communications", "Advanced integrated circuit design and fabrication", "Highest institution rank for United States", "High performance computing", "Protective cyber security technologies", "Distributed ledgers", "Natural language processing", and "Machine learning".

In the "Energy and environment" category, they have "Supercapacitors", "Nuclear waste management and recycling", "Nuclear energy", "Photovoltaics", "Hydrogen and ammonia for power", "Directed energy technologies", "Biofuels", and "Electric batteries".

In the "Advanced materials & manufacturing" category, they have "Smart materials", "Novel metamaterials", "Highest country rank for United States", "Highest institution rank for United States", "Nanoscale materials and manufacturing", "Critical minerals extraction and processing", "Advanced magnets and superconductors", "High-specification machining processes", "Advanced explosives and energetic materials", "Coatings", "Continuous flow chemical synthesis", "Advanced protection", "Advanced composite materials", and "Additive manufacturing".

In the "Biotechnology, gene technologies and vaccines", category, they have "Vaccines and medical countermeasures", "Synthetic biology", "Highest country rank for United States", "Highest institution rank for United States", and "Biological manufacturing".

In the "Quantum" category, they have "Quantum sensors", "Post-quantum cryptography", "Quantum communications", and "Quantum computing".

When you do a comparison, there are 3 tabs, "Flow of human talent", "Research Contribution", and "Insights".

In the "Flow of human talent" section, it shows the flow of people between countries as they go from "Undergraduate", to "Postgraduate" to "Employment".

In "Research Contribution", it shows rankings in the category you chose ranked as "Countries ranked by highest H-index" and "Proportion of publications in top 10%".

The insights tab has their own commentary.

"Singapore performs very well, attracting researchers particularly from India and China to its two field-leading universities, the National University of Singapore and the Nanyang Technological University. The research that emerges from these Singaporean institutions places Singapore as one of the top countries in AI algorithms and hardware accelerators."

ASPI's Critical Technology Tracker

#solidstatelife #ai #quantumcomputing #robotics #space #energy #biotech #china #geopolitics

2 Likes
1 Shares
smokeinfog@diasp.org
SmokeInFog

Strange new phase of matter created in quantum computer acts like it has two time dimensions

By shining a laser pulse sequence inspired by the Fibonacci numbers at atoms inside a quantum computer, physicists have created a remarkable, never-before-seen phase of matter. The phase has the benefits of two time dimensions despite there still being only one singular flow of time, the physicists report July 20 in Nature.

This mind-bending property offers a sought-after benefit: Information stored in the phase is far more protected against errors than with alternative setups currently used in quantum computers. As a result, the information can exist without getting garbled for much longer, an important milestone for making quantum computing viable, says study lead author Philipp Dumitrescu.

The approach's use of an "extra" time dimension "is a completely different way of thinking about phases of matter," says Dumitrescu, who worked on the project as a research fellow at the Flatiron Institute's Center for Computational Quantum Physics in New York City. "I've been working on these theory ideas for over five years, and seeing them come actually to be realized in experiments is exciting."

Dumitrescu spearheaded the study's theoretical component with Andrew Potter of the University of British Columbia in Vancouver, Romain Vasseur of the University of Massachusetts, Amherst, and Ajesh Kumar of the University of Texas at Austin. The experiments were carried out on a quantum computer at Quantinuum in Broomfield, Colorado, by a team led by Brian Neyenhuis.

The workhorses of the team's quantum computer are 10 atomic ions of an element called ytterbium. Each ion is individually held and controlled by electric fields produced by an ion trap, and can be manipulated or measured using laser pulses.

Each of those atomic ions serves as what scientists dub a quantum bit, or "qubit." Whereas traditional computers quantify information in bits (each representing a 0 or a 1), the qubits used by quantum computers leverage the strangeness of quantum mechanics to store even more information. Just as Schrödinger's cat is both dead and alive in its box, a qubit can be a 0, a 1 or a mashup—or "superposition"—of both. That extra information density and the way qubits interact with one another promise to allow quantum computers to tackle computational problems far beyond the reach of conventional computers.

There's a big problem, though: Just as peeking in Schrödinger's box seals the cat's fate, so does interacting with a qubit. And that interaction doesn't even have to be deliberate. "Even if you keep all the atoms under tight control, they can lose their quantumness by talking to their environment, heating up or interacting with things in ways you didn't plan," Dumitrescu says. "In practice, experimental devices have many sources of error that can degrade coherence after just a few laser pulses."

The challenge, therefore, is to make qubits more robust. To do that, physicists can use "symmetries," essentially properties that hold up to change. (A snowflake, for instance, has rotational symmetry because it looks the same when rotated by 60 degrees.) One method is adding time symmetry by blasting the atoms with rhythmic laser pulses. This approach helps, but Dumitrescu and his collaborators wondered if they could go further. So instead of just one time symmetry, they aimed to add two by using ordered but non-repeating laser pulses.

The best way to understand their approach is by considering something else ordered yet non-repeating: "quasicrystals." A typical crystal has a regular, repeating structure, like the hexagons in a honeycomb. A quasicrystal still has order, but its patterns never repeat. (Penrose tiling is one example of this.) Even more mind-boggling is that quasicrystals are crystals from higher dimensions projected, or squished down, into lower dimensions. Those higher dimensions can even be beyond physical space's three dimensions: A 2D Penrose tiling, for instance, is a projected slice of a 5-D lattice.

For the qubits, Dumitrescu, Vasseur and Potter proposed in 2018 the creation of a quasicrystal in time rather than space. Whereas a periodic laser pulse would alternate (A, B, A, B, A, B, etc.), the researchers created a quasi-periodic laser-pulse regimen based on the Fibonacci sequence. In such a sequence, each part of the sequence is the sum of the two previous parts (A, AB, ABA, ABAAB, ABAABABA, etc.). This arrangement, just like a quasicrystal, is ordered without repeating. And, akin to a quasicrystal, it's a 2D pattern squashed into a single dimension. That dimensional flattening theoretically results in two time symmetries instead of just one: The system essentially gets a bonus symmetry from a nonexistent extra time dimension.

Actual quantum computers are incredibly complex experimental systems, though, so whether the benefits promised by the theory would endure in real-world qubits remained unproven.

Using Quantinuum's quantum computer, the experientialists put the theory to the test. They pulsed laser light at the computer's qubits both periodically and using the sequence based on the Fibonacci numbers. The focus was on the qubits at either end of the 10-atom lineup; that's where the researchers expected to see the new phase of matter experiencing two time symmetries at once. In the periodic test, the edge qubits stayed quantum for around 1.5 seconds—already an impressive length given that the qubits were interacting strongly with one another. With the quasi-periodic pattern, the qubits stayed quantum for the entire length of the experiment, about 5.5 seconds. That's because the extra time symmetry provided more protection, Dumitrescu says.

"With this quasi-periodic sequence, there's a complicated evolution that cancels out all the errors that live on the edge," he says. "Because of that, the edge stays quantum-mechanically coherent much, much longer than you'd expect."

Though the findings demonstrate that the new phase of matter can act as long-term quantum information storage, the researchers still need to functionally integrate the phase with the computational side of quantum computing. "We have this direct, tantalizing application, but we need to find a way to hook it into the calculations," Dumitrescu says. "That's an open problem we're working on."

#quantumComputing #quantumMechanics #physics #computer #science #quasicrystal #PhysOrg

Strange new phase of matter created in quantum computer acts like it has two time dimensions

By shining a laser pulse sequence inspired by the Fibonacci numbers at atoms inside a quantum computer, physicists have created a remarkable, never-before-seen phase of matter. The phase has the benefits of two time dimensions despite there still...

4 Likes
1 Comments