Browsing by Author "Bencivenga, Dante"

Now showing 1 - 2 of 2
  • Thumbnail Image
    ItemOpen Access
    Faster Randomized Repeated Choice and DCAS
    (ACM, 2024) Bencivenga, Dante; Giakkoupis, George; Woelfel, Philipp
    At STOC 2021, Giakkoupis, Giv, and Woelfel, presented an efficient randomized implementation of Double Compare-And-Swap (DCAS) from Compare-And-Swap (CAS) objects. DCAS is a useful and fundamental synchronization primitive for shared memory systems, which, contrary to CAS, is not available in hardware. The DCAS algorithm has O(logn) expected amortized step complexity against an oblivious adversary, where nn is the number of processes in the system. The bottleneck of this algorithm is a building block, introduced in the same paper: A repeated choice (RC) object, which allows processes to propose values, and later agree on (and “lock in”) one of the proposed values, which is roughly uniformly distributed among the “recently” proposed ones. The object can then be unlocked, and the process be repeated. The RC implementation introduced by Giakkoupis et al. has step complexity O(logn). In this paper, we present a more efficient RC algorithm, with similar probabilistic guarantees, but expected step complexity O(loglogn). We then show how this improved RC object can be used to achieve an exponential improvement in the expected amortized step complexity of DCAS.
  • Thumbnail Image
    ItemOpen Access
    Sampling Using Controlled Quantum Walks
    (2020-10-26) Bencivenga, Dante; Høyer, Peter; Feder, David; Woelfel, Philipp
    We give a new quantum algorithm to sample from probability distributions over graph vertices quadratically faster than the optimal classical algorithm, which uses random walks with stopping rules. Efficient sampling is an important computational task used in simulations based on stochastic processes. This is the first quantum algorithm that achieves a quadratic speed-up for sampling from general probability distributions over graph vertices. Our algorithm generalizes the controlled quantum walk algorithm proposed by Dohotaru and Høyer in 2015. Our main technical innovation is to allow for multiple distinct controlled reflections. This allows us to generate the quantum state analogous to the target probability distribution over vertices. This quantum state, when measured, gives a corresponding classical sample from the target distribution. We also give a second classical algorithm for sampling from probability distributions over graph vertices. This algorithm adds different self-loops to each vertex of the random walk. We show how to construct the quantum analogue of this algorithm. Finally, we show that we can embed this quantum analogue into our controlled quantum walk.