Polynomial-time Classical Simulation of Roetteler’s Shifted Bent Function Algorithm (PLanQC 2024) - POPL 2024

Sun 14 - Sat 20 January 2024 London, United Kingdom

Who

Lucas Stinchcombe, Matthew Amy

Track

Time Zone

The program is currently displayed in (GMT) London.

Use conference time zone: (GMT) LondonSelect other time zone

The GMT offsets shown reflect the offsets at the moment of the conference.

Time Band

By setting a time band, the program will dim events that are outside this time window. This is useful for (virtual) conferences with a continuous program (with repeated sessions).
The time band will also limit the events that are included in the personal iCalendar subscription service.

Display full programSpecify a time band

When

Sat 20 Jan 2024 11:45 - 12:07 at Marconi Room - Compilation Chair(s): Ross Duncan

Abstract

We show that Roetteler’s shifted bent function algorithm is polynomial-time simulable when implemented by the construction of Bravyi and Gosset. We do this by giving a classical simulation procedure based on symbolic rewriting of a circuit’s sum-over-paths and show that every sequence of rewrites terminates with the hidden the shift in time polynomial in the volume of the circuit.

Lucas Stinchcombe

Simon Fraser University

Matthew Amy

Simon Fraser University

Canada

Time Zone

The program is currently displayed in (GMT) London.

Use conference time zone: (GMT) LondonSelect other time zone

The GMT offsets shown reflect the offsets at the moment of the conference.

Time Band

By setting a time band, the program will dim events that are outside this time window. This is useful for (virtual) conferences with a continuous program (with repeated sessions).
The time band will also limit the events that are included in the personal iCalendar subscription service.

Display full programSpecify a time band

Session Program

Sat 20 Jan
Displayed time zone: London change

	11:00 - 12:30	CompilationPLanQC at Marconi Room Chair(s): Ross Duncan Quantinuum

	11:00 22m Talk		Graphical Primitive Recursion For String Diagrams PLanQC Zhulien Zhelezchev University of Bristol, Aleks Kissinger University of Oxford
	11:22 22m Talk		Optimal compilation of parametrised quantum circuits PLanQC John van de Wetering University of Amsterdam, Richie Yeung University of Oxford, Tuomas Laakkonen Quantinuum, Aleks Kissinger University of Oxford
	11:45 22m Talk		Polynomial-time Classical Simulation of Roetteler’s Shifted Bent Function Algorithm PLanQC Lucas Stinchcombe Simon Fraser University, Matthew Amy Simon Fraser University
	12:07 22m Talk		Qadence: a differentiable interface for digital-analog programs PLanQC Dominik Seitz PASQAL SAS, Niklas Heim PASQAL SAS, João P. Moutinho PASQAL SAS, Roland Guichard PASQAL SAS, Vytautas Abramavicius PASQAL SAS, Aleksander Wennersteen PASQAL SAS, Gert-Jan Both PASQAL SAS, Mario Dagrada PASQAL SAS, Vincent Elfving PASQAL SAS Pre-print File Attached