While mapping a quantum circuit to the physical layer one has to consider the numerous constraints imposed by the underlying hardware architecture. Connectivity of the physical qubits is one such constraint that restricts two-qubit operations, such as CNOT, to “connected” qubits. SWAP gates can be used to place the logical qubits on admissible physical qubits, but they entail a significant increase in CNOT-count. In this article, we consider the problem of reducing the CNOT-count in Clifford+T circuits on connectivity-constrained architectures, like noisy intermediate-scale quantum (NISQ) computing devices. We “slice” the circuit at the position of Hadamard gates and “build” the intermediate$\{\text {CNOT},{T}\}$subcircuits using Steiner trees, significantly improving on previous methods. We compared the performance of our algorithms while mapping different benchmark and random circuits to some well-known architectures, such as 9-qubit square grid, 16-qubit square grid, Rigetti 16-qubit Aspen, 16-qubit IBM QX5, and 20-qubit IBM Tokyo. Our methods give less CNOT-count compared to Qiskit and TKET transpiler as well as using SWAP gates. Assuming most of the errors in an NISQ circuit implementation are due to CNOT errors, then our method would allow circuits with a few times more CNOT gates be reliably implemented than the previous methods would permit.

Ajtai, Kumar and Sivakumar [Ajtai et al., 2001] gave the first 2^O(n) algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices. The algorithm starts with N in 2^O(n) randomly chosen vectors in the lattice and employs a sieving procedure to iteratively obtain shorter vectors in the lattice, and eventually obtaining the shortest non-zero vector. The running time of the sieving procedure is quadratic in N. Subsequent works [Arvind and Joglekar, 2008; Blömer and Naewe, 2009] generalized the algorithm to other norms. We study this problem for the special but important case of the l_infty norm. We give a new sieving procedure that runs in time linear in N, thereby improving the running time of the algorithm for SVP in the l_infty norm. As in [Ajtai et al., 2002; Blömer and Naewe, 2009], we also extend this algorithm to obtain significantly faster algorithms for approximate versions of the shortest vector problem and the closest vector problem (CVP) in the l_infty norm. We also show that the heuristic sieving algorithms of Nguyen and Vidick [Nguyen and Vidick, 2008] and Wang et al. [Wang et al., 2011] can also be analyzed in the l_infty norm. The main technical contribution in this part is to calculate the expected volume of intersection of a unit ball centred at origin and another ball of a different radius centred at a uniformly random point on the boundary of the unit ball. This might be of independent interest.

Let the randomized query complexity of a relation for error probability epsilon be denoted by R_epsilon(). We prove that for any relation f contained in {0,1}^n times R and Boolean function g:{0,1}^m -> {0,1}, R_{1/3}(f o g^n) = Omega(R_{4/9}(f).R_{1/2-1/n^4}(g)), where f o g^n is the relation obtained by composing f and g. We also show using an XOR lemma that R_{1/3}(f o (g^{xor}_{O(log n)})^n) = Omega(log n . R_{4/9}(f) . R_{1/3}(g))$, where g^{xor}_{O(log n)} is the function obtained by composing the XOR function on O(log n) bits and g.

In this paper, we present the following quantum compression protocol `P': Let ρ,σ be quantum states, such that S (ρ∥σ)def= Tr(ρ log ρ - ρ log σ), the relative entropy between ρ and σ, is finite. Alice gets to know the eigendecomposition of ρ. Bob gets to know the eigendecomposition of σ. Both Alice and Bob know S(ρ∥σ) and an error parameter ε. Alice and Bob use shared entanglement and after communication of O((S(ρ∥σ) + 1)/ε4) bits from Alice to Bob, Bob ends up with a quantum state ̃ρ̃, such that F(ρ, ρ̃) ≥ 1-5ε, where F(·) represents fidelity. This result can be considered as a non-commutative generalization of a result due to Braverman and Rao where they considered the special case when ρ and σ are classical probability distributions (or commute with each other) and use shared randomness instead of shared entanglement. We use? to obtain an alternate proof of a direct-sum result for entanglement assisted quantum one-way communication complexity for all relations, which was first shown by Jain et al.. We also present a variant of protocol? in which Bob has some side information about the state with Alice. We show that in such a case, the amount of communication can be further reduced, based on the side information that Bob has. Our second result provides a quantum analog of the widely used classical correlated-sampling protocol. For example, Holenstein used the classical correlated-sampling protocol in his proof of a parallel-repetition theorem for two-player one-round games.