Manideep Mamindlapally

Stacey Jeffery, Manideep Mamindlapally, Alex Baudoin Nguetsa Tankeu

The quantum circuit model essentially treats every quantum algorithm as a straight-line program. While this view is universal, recent work has shown that it is inconvenient for using different-length quantum subroutines in superposition. Using the quantum walk formalism of quantum algorithms, it is possible to model such branching behaviour, and get better composition in this setting. We apply the above branching composition to Grover's algorithm, which gives a variable-time quantum search algorithm that is worse than previous work. The reason it is worse is because branching composition does not take into account another deviation from straight-line programs: looping. We show that by modifying branching composition to also include looping, we can get a complexity that matches previous work. This highlights the importance of properly modeling the program control flow when designing quantum algorithms.

Amitalok J. Budkuley, Pranav Joshi, Manideep Mamindlapally et al.

Commitment is an important cryptographic primitive. It is well known that noisy channels are a promising resource to realize commitment in an information-theoretically secure manner. However, oftentimes, channel behaviour may be poorly characterized thereby limiting the commitment throughput and/or degrading the security guarantees; particularly problematic is when a dishonest party, unbeknown to the honest one, can maliciously alter the channel characteristics. Reverse elastic channels (RECs) are an interesting class of such unreliable channels, where only a dishonest committer, say, Alice can maliciously alter the channel. RECs have attracted recent interest in the study of several cryptographic primitives. Our principal contribution is the REC commitment capacity characterization; this proves a recent related conjecture. A key result is our tight converse which analyses a specific cheating strategy by Alice. RECs are closely related to the classic unfair noisy channels (UNCs); elastic channels (ECs), where only a dishonest receiver Bob can alter the channel, are similarly related. In stark contrast to UNCs, both RECs and ECs always exhibit positive commitment throughput for all non-trivial parameters. Interestingly, our results show that channels with exclusive one-sided elasticity for dishonest parties, exhibit a fundamental asymmetry where a committer with one-sided elasticity has a more debilitating effect on the commitment throughput than a receiver.