Our Publications

Efficient unstructured search implementation on current ion-trap quantum processors

Vladyslav Hlembotskyi, Rafał Burczyński, Witold Jarnicki, Adam Szady, Jan Tułowiecki

So far, only the results on 3 qubit spaces (both on superconducting and ion-trap realisations of quantum processors) have beaten the classical unstructured search in the expected number of oracle calls using optimal protocols in both settings. We present experimental results on running unstructured search in spaces defined by 4, 5 and 6 qubits on ion-trapped quantum processor. Our best circuits obtained respectively 66\%, 26\% and 6\% average probability of measuring the marked element. In the case of 4 and 5 qubit spaces we obtained fewer expected number of oracle calls required to find a marked element than any classical approach. Viability of the theoretical result by Grover at these qubit counts is, to authors' knowledge demonstrated experimentally for the first time. Also at 6 qubits, a circuit using a single oracle call returned a measured probability of success exceeding any possible classical approach. These results were achieved using a variety of unstructured search algorithms in conjunction with recent developments in reducing the number of entangling gates. The latter are currently considered to be a dominating source of errors in quantum computations. Some of these improvements have been made possible by using mid-circuit measurements. To our knowledge the latter feature is currently available only on the H0 quantum processor we run on.

Pdf Publication can be found here

Benchmarking 16-element quantum search algorithms on IBM quantum processors

Jan Gwinner, Marcin Briański, Wojciech Burkot, Łukasz Czerwiński, Vladyslav Hlembotskyi, July 13, 2020

We present experimental results on running 4-qubit unstructured search on IBM quantum processors. Our best attempt attained probability of success around 24.5%. We try several algorithms and use the most recent developments in quantum search to reduce the number of entangling gates that are currently considered the main source of errors in quantum computations. Comparing theoretical expectations of an algorithm performance with the actual data, we explore the hardware limits, showing sharp, phase-transition-like degradation of performance on quantum processors. We conclude that it is extremely important to design hardware-aware algorithms and to include any other low level optimizations on NISQ devices.

Pdf Publication can be found here

Introducing Structure to Expedite Quantum Search

Marcin Briański, Jan Gwinner, Vladyslav Hlembotskyi, Witold Jarnicki, Szymon Pliś, Adam Szady, June 10, 2020

We present a novel quantum algorithm for solving the unstructured search problem with one marked element. Our algorithm allows generating quantum circuits that use asymptotically fewer additional quantum gates than the famous Grover's algorithm and may be successfully executed on NISQ devices. We prove that our algorithm is optimal in the total number of elementary gates up to a multiplicative constant. As many NP-hard problems are not in fact unstructured, we also describe the partial uncompute technique which exploits the oracle structure and allows a significant reduction in the number of elementary gates required to find the solution. Combining these results allows us to use asymptotically smaller number of elementary gates than the Grover's algorithm in various applications, keeping the number of queries to the oracle essentially the same. We show how the results can be applied to solve hard combinatorial problems, for example Unique k-SAT. Additionally, we show how to asymptotically reduce the number of elementary gates required to solve the unstructured search problem with multiple marked elements.

Pdf Publication can be found here

Quantum Computing Algorithms for NISQ Era

Wojciech Burkot, Quantum Computing Meetup, Washington, DC, May 15th, 2020

A talk about a family of algorithms especially constructed for NISQ computers promising much better results at currently available qubit counts and circuit depths.

Pdf Presentation slides can be found here

A short note on graphs with long Thomason's chains

Marcin Briański, Adam Szady, March 6, 2019

We present a family of 3-connected cubic planar Hamiltonian graphs with an exponential number of steps required by Thomason's algorithm. The base of the exponent is approximately 1.1812…, which exceeds previous results in the area.

Pdf Publication can be found here

Quantum Boltzmann sampling – noisiness of some existing hardware approaches

Witold Jarnicki, Q2B Conference, Mountain View, CA, December 10–12, 2018

Investigation of the distribution of samples produced by existing methods of sampling from a quantum Boltzmann distrubution and comparision them to purely theoretical values.

Pdf Presentation slides can be found here

YouTube YouTube video can be found here

Quantum gates definition and decomposition

Jupyter notebook with useful quantum utilities can be found here