4 Replies - 1164 Views - Last Post: 22 October 2018 - 06:36 PM

#1 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12390
  • View blog
  • Posts: 45,519
  • Joined: 27-December 08

[News] First Proof of Quantum Supremacy

Post icon  Posted 19 October 2018 - 09:35 AM

For those unfamiliar, Quantum Computation is a theoretical model of computing that leverages quantum mechanics to perform computations. Quantum computing is particularly effective at solving number theoretic and algebraic problems, such as factoring integers (Shor's algorithm). Much of our cryptography (e.g., RSA) is based on the (unproven) assumption that factoring is a hard problem. Similarly, Quantum computing is also effective at searching through unstructured data (Grover's algorithm). Despite the interest in this area, these are the two major algorithmic breakthroughs in quantum.

Based on these algorithms, it is widely believed that quantum computing is more efficient than classical computation, though proofs of such claims have been elusive. The authors of this paper provide the first provable instance of quantum supremacy, which is a *major* result.

Quote

Quantum effects can enhance information-processing capabilities and speed up the solution of certain computational problems. Whether a quantum advantage can be rigorously proven in some setting or demonstrated experimentally using near-term devices is the subject of active debate. We show that parallel quantum algorithms running in a constant time period are strictly more powerful than their classical counterparts; they are provably better at solving certain linear algebra problems associated with binary quadratic forms. Our work gives an unconditional proof of a computational quantum advantage and simultaneously pinpoints its origin: It is a consequence of quantum nonlocality. The proposed quantum algorithm is a suitable candidate for near-future experimental realizations, as it requires only constant-depth quantum circuits with nearest-neighbor gates on a two-dimensional grid of qubits (quantum bits).



http://science.scien...50NqcR5v3fPh0_M

Is This A Good Question/Topic? 3
  • +

Replies To: [News] First Proof of Quantum Supremacy

#2 Martyr2   User is offline

  • Programming Theoretician
  • member icon

Reputation: 5309
  • View blog
  • Posts: 14,172
  • Joined: 18-April 07

Re: [News] First Proof of Quantum Supremacy

Posted 19 October 2018 - 09:42 AM

I will hold judgement until the results can be independently verified and reproduced. ;)
Was This Post Helpful? 0
  • +
  • -

#3 hexagod   User is offline

  • D.I.C Regular

Reputation: 11
  • View blog
  • Posts: 354
  • Joined: 29-October 16

Re: [News] First Proof of Quantum Supremacy

Posted 22 October 2018 - 08:05 AM

IT's going to be interesting to see what this does to the field of cryptography.
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12390
  • View blog
  • Posts: 45,519
  • Joined: 27-December 08

Re: [News] First Proof of Quantum Supremacy

Posted 22 October 2018 - 10:28 AM

We actually already know what effects quantum will have on cryptography. And there is work on quantum-secure cryptography.

I donít believe this result will specifically impact quantum cryptography.
Was This Post Helpful? 1
  • +
  • -

#5 hexagod   User is offline

  • D.I.C Regular

Reputation: 11
  • View blog
  • Posts: 354
  • Joined: 29-October 16

Re: [News] First Proof of Quantum Supremacy

Posted 22 October 2018 - 06:36 PM

I saw a documentary on quantum encryption via quantum entanglement... completely unfathomable, but still way cool. I think the good will win over the bad. The good wants to keep your data and crypto private; the bad wants to steal it. We outnumber them. The good will prevail (imo)

This post has been edited by hexagod: 22 October 2018 - 06:37 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1