Program
Full Program | Sunday | Monday | Tuesday | All Sessions | Posters | Talks
SESSION 2: Computer scienceChair: (Elizabeth Crosson) | |
10:45am - 11:30am | Anne Broadbent, University of Ottawa (invited) Uncloneable encryption | Abstract. In 2002, Gottesman answered this question in the positive, proposing a quantum encryption scheme for classical messages, with a decryption process that detects any attempt to copy the ciphertext. Clearly, classical information alone does not allow such a functionality, since it is always possible to perfectly copy a classical ciphertext while avoiding detection. However, Gottesman left open the question of restricting the knowledge that two recipients could simultaneously have on a plaintext, after an attack on a single ciphertext. Here, we address this open question by showing that Wiesner's conjugate coding can be used to achieve this type of uncloneable encryption for classical messages. Our approach is a prepare-and-measure scheme and the analysis is done in the quantum random oracle model, using techniques from the analysis of monogamy-of-entanglement games. |
11:30am - 12:00pm | Yigit Subasi, Los Alamos National Laboratory Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing | Abstract. We present two quantum algorithms based on evolution randomization, a simple variant of adiabatic quantum computing, to prepare a quantum state \(ket{x}\) that is proportional to the solution of the system of linear equations \(A \vec{x}=\vec{b}\). The time complexities of our algorithms are \(O(\kappa^2 \log(\kappa)/\epsilon)\) and \(O(\kappa \log(\kappa)/\epsilon)\) where \(\kappa \) is the condition number of \(A\) and \(\epsilon\) is the precision. Both algorithms are constructed using families of Hamiltonians that are linear combinations of products of \(A\), the projector onto the initial state \(|b>\), and single-qubit Pauli operators. The algorithms are conceptually simple and easy to implement. They are not obtained from equivalences between the gate model and adiabatic quantum computing, and do not use phase estimation or variable-time amplitude amplification. We describe a gate-based implementation via Hamiltonian simulation and prove that our second algorithm is almost optimal in terms of \(\kappa \). Like previous methods, our techniques yield an exponential quantum speed-up under some assumptions. Our results emphasize the role of Hamiltonian-based models of quantum computing for the discovery of important algorithms. |
- Home
- SQuInT
- Registration
- Program
- Instructions for Presenters
- Survey
- Lodging and Transportation
- Hotel Floor Maps (.pdf)
- Faculty Favorites at Old Town
- Past SQuInT Meetings
SQuInT Chief Organizer
Akimasa Miyake, Associate Professor
amiyake@unm.edu
Rafael Alexander, Postdoctoral Fellow
Chris Jackson, Postdoctoral Fellow
SQuInT Administrator
Gloria Cordova
gjcordo1@unm.edu
505 277-1850
SQuInT Assistant
Wendy Jay
SQuInT Founder
Ivan Deutsch, Regents' Professor, CQuIC Director
ideutsch@unm.edu