Quantum Position Verification, Quantum Nonlocal Computation, and Surprising Connections with Holography and Classical Cryptography

University of Amsterdam

HARRY BUHRMAN

QFort Workshop

16-4-2024

QUANTINUUM

World’s Leading Quantum Computing Company

FULL STACK

InQuanto™ Quantum chemistry software. TKET™ open-source developer tool kit. LAMBEQ™ open-source natural language processing

Collaborations and partnership with leading commercial and academic organization

>1,500,000

Downloads of TKET™ open-source tool kit

350+

scientists and engineers

(of which > 200PhDs)

>80

Scientific publications using H-Series hardware

H-SERIES

World class QCCD, ion trap hardware with industry-leading fidelity and scalability

LARGEST�PLAYER

in integrated quantum �hardware and software

WHO WE ARE

WHAT WE OFFER

USER COMMUNITY

> 400

Global users of H-Series hardware

CUSTOMERS & PARTNERS

Premier financial institutions:  

JPMC | HSBC

Top industrials: HONEYWELL | BMW | AIRBUS

US Department of Energy Labs

Cloud service partner:

MICROSOFT AZURE QUANTUM

Quantinuum at-a-glance

Introducing H2

The world’s most powerful quantum computer

• 32 fully connected qubits
• 99.997% single-qubit gate fidelity
• 99.9% two-qubit gate fidelity

Includes all-to-all connectivity, mid-circuit measurement with conditional logic, qubit reuse, arbitrary angle 2-qubit gates

Highest performing

Most Benchmarked

Enabling what no other hardware can do

H-series: the #1 QPU platform

>1,000x QV¹

• Conditional logic
• All-to-all connectivity
• Long coherence times
• Qubit reuse
• Low cross-talk mid-circuit measurement

​

18 benchmarks tested

​

All documented on GitHub

The state of the art today

System Model H2 ion-trap based on the QCCD architecture

32 qubits transported around the ion-trap 'racetrack'

Jenni

Created�the most reliable �logical qubits on record

Performed multiple successful active syndrome extractions

Achieved 800x improvement in logical error rate over physical

Putting theory into practice:

Demonstrating the next level of reliable quantum computing

Krysta

FIRST QUANTUM APPLICATIONS

• Factorizing numbers [Shor]
• Breaks frequently used cryptography
• Quantum cryptography [Bennett-Brassard-Ekert]
• Quantum-proof cryptography
• Efficient communication
• Quantum internet, entanglement etc.
• Simulation of nature
• Chemistry, material design, new medicines..
• Optimization problems, Machine learning
• Applications for society & industry
• Quantum inspired algorithms
• Machine learning, recommendation systems, optimization …

​

​

​

Rene Allerstorfer

Wolgang Loeffler

Kirstin Kannenwerf

Alex May

Philip Verduyn-Lunel

Florian Speelman

Based on joint work with

© 2024 Quantinuum

NASA

The Great Moon-Landing Hoax?

• How can you prove that you are at a specific location?

http://www.unmuseum.org/moonhoax.htm

1969: MAN ON THE MOON

POSITION VERIFICATION

• Prove you are at a certain position
• launching-missile command comes from within the Pentagon
• talking to South-Korea and not North-Korea
• pizza delivery problem
• building block for other cryptographic tasks
• authentication, position-based key-exchange
• Can only decipher message at specific location

​

POSITION VERIFICATION�ONE-DIMENSIONAL CASE�

POSITION VERIFICATION

• Prover convince verifiers he is at particular position
• assumptions:
• communication at speed of light
• instantaneous computation
• verifiers can coordinate
• no coalition of (fake) provers, not at the claimed position, can convince verifiers

POSITION VERIFICATION: FIRST TRY

Verifier 0

Prover

distance bounding [Brands-Chaum’93]

POSITION VERIFICATION: SECOND TRY

position verification is classically impossible! even using computational assumptions

[Chandran Goyal Moriarty

Ostrovsky’09]

Prover

Verifier 0

EQUIVALENT GAME �FOR THE ATTACK��

m_x =x

EQUIVALENT ATTACKING GAME

x

y

m_x

m_y=y

a

b

messages m_x and m_y

independent of each other

m_y

copying classical information

not possible quantumly

QUANTUM PROTOCOLS���

QUANTUM ATTEMPT

Verifier 0

Prover

send to

Verifier b

if b=1

if b=0

random qubit

Let’s study attacking game

for Alice & Bob

ATTACKING GAME

if b=1

if b=0

b

& b=1

impossible!

[Chandran et.al. 2010]

possible with entanglement

TELEPORTATION���

TELEPORTATION

quantum

measurement

outcome

two bits

c₁, c₂

c₁, c₂

EPR-pair

transform

instantaneous!!

 [Bennett, Brassard, Crépeau, Jozsa, Peres, Wootters ‘93]

ENTANGLEMENT ATTACK

teleportation

c₁, c₂

b

protocol

teleportation

d₁, d₂

b,d₁,d₂

c₁, c₂

• b=1 keep

• teleport

• b=0 recover

• b=0 teleport back

recover

26

MORE COMPLICATED SCHEMES?

• Different schemes proposed
• Chandran, Fehr, Gelles, Goyal, Ostrovsky [2010]
• Malaney [2010]
• Kent, Munro, Spiller [2010]
• Lau, Lo [2010]
• Unfortunately they can all be broken
• general no-go theorem [B,Chandran,Fehr,Gelles,Goyal, Ostrovsky, Schaffner 2010]
• More efficiënt attack [Beigi-König 2011 ]
• Proof uses teleportation & port-based teleportation
• Exponential amount of entanglement

NO-GO THEOREM

• Any position-verification protocol broken with exponential # of EPR-pairs
• Best lower bound: linear # of EPR-pairs
• Question 1: is there a better lower bound?
• exist a protocol:
• attack requires many EPR-pairs
• honest prover & verifiers efficient
• Question 2: Realize protocols experimentally
• deal with imperfections and errors
• photon loss, errors, actual speed of light etc.

​

Surprising connections with:

• Computational Complexity Theory
• Classical Cryptography
• String Theory
• Functional Analysis

EFFICIENT SINGLE-QUBIT PROTOCOL����

SINGLE-QUBIT PROTOCOL: F-ROUTING

Verifier 0

Prover

send to

Verifier f(x,y)

if f(x,y)=1

if f(x,y)=0

efficiently computable

[Kent-Munro-Spiller

2010]

ATTACKING GAME FOR F-ROUTING

if f(x,y)=1

if f(x,y)=0

COMPUTATIONAL COMPLEXITY INTUITION FOR ATTACK

In all these settings:

• Best upper bound exponential
• Best lower bound linear

ADS/CFT CORRESPONDENCE�CHALLENGES INTUITION������

32

ADS/CFT CORRESPONDANCE

ADS Bulk

CFT

boundary

correspondence

Anti-de Sitter Space

Conformal Field Theory

model of spacetime used in theories of gravity

quantum field theory invariant under conformal transformations

Correspondence Tool for

• Quantum Gravity
• Black Hole Physics: Quantum Chromodynamics
• Condensed Matter Physics

3D

2D

ADS/CFT

• Intriguing connection with ADS/CFT [May’21, Dolev-Cree’22]

​

​

​

​

​

​

​

�

ADS Bulk

Honest QPV protocol

CFT

boundary

Attack on QPV protocol

(non-local computation)

correspondence

• What about the other barriers in CS?
• Are they connected to QPV?
• Does ADS/CFT have baring on them?

CLASSICAL CRYPTOGRAPHY�������

Conditional Disclosure of Secrets �(CDS)

shared random bits

Example: XOR

Conditional Disclosure of Secrets �(CDS)

shared random bits

Conditional Disclosure of Secrets �(CDQS)

Purify the protocol

Conditional Disclosure of Secrets �(CDQS)

Purify the protocol

Conditional Disclosure of Secrets �(CDQS)

Purify the protocol

A-register

B-register

More Connections

Inversion 1

• Attacks on QPV: communication game

​

Inversion 2

• Efficient QCDS equivalent communication

game

[Allerstorfer-Buhrman-May-Speelman-Verduyn Lunel’23]

upper and lower bounds in complexity theory:

good upper bounds yield strong lower bounds

Quantum Position Verification

We get one of the two:

1. Secure QPV protocol
2. Efficient QCDS

SUMMARY

• Quantum Position Verification
• Not possible Classical,
• Not possible Quantum, but attack seems to need exponential resources
• Simple protocol: f-routing
• Security for f in P tie in with unresolved complexity theoretical questions
• Connected with classical cryptographic protocols: CDS, Secret sharing, PSM
• CS intuition is that f-routing is secure for functions in Polynomial time.
• ADS/CFT intuition: not secure
• Many open problems remain!
• Separate stream designing efficient and secure implementations