Quantum signal processing (QSP), which is a general technique for construction of 1-qubit rotation operators, is a strong framework for quantum algorithm design. We consider a scenario of information-theoretically secure computation for QSP: n parties who have private angle parameters make the evaluator perform the QSP from the sum of their angles in a privacy-preserving manner through noninteractive communication. In this scenario, we construct a private simultaneous messages (PSM) protocol for QSP, named Private QSP (PQSP). As an application, we construct an efficient PSM protocol for symmetric Boolean functions with an evaluator of 1-qubit workspace by adapting PQSP to the 1-qubit quantum algorithm for symmetric Boolean functions of Maslov et al. [1]. We also show that the technique of PQSP works for the 1-qubit program for Boolean functions of Cosentino et al. [2]. We construct an efficient PSM protocol for Boolean functions computable by O(log n)-depth circuits with an evaluator of 1-qubit writable workspace from their 1-qubit program [3]. Such efficient PSM protocols with space-bounded classical evaluators have not been known so far.
Quantum signal processing (QSP), which is a general technique for construction of 1-qubit rotation operators, is a strong framework for quantum algorithm design. We consider a scenario of information-theoretically secure computation for QSP: n parties who have private angle parameters make the evaluator perform the QSP from the sum of their angles in a privacy-preserving manner through noninteractive communication. In this scenario, we construct a private simultaneous messages (PSM) protocol for QSP, named Private QSP (PQSP). As an application, we construct an efficient PSM protocol for symmetric Boolean functions with an evaluator of 1-qubit workspace by adapting PQSP to the 1-qubit quantum algorithm for symmetric Boolean functions of Maslov et al. [1]. We also show that the technique of PQSP works for the 1-qubit program for Boolean functions of Cosentino et al. [2]. We construct an efficient PSM protocol for Boolean functions computable by O(log n)-depth circuits with an evaluator of 1-qubit writable workspace from their 1-qubit program [3]. Such efficient PSM protocols with space-bounded classical evaluators have not been known so far.
The private simultaneous messages model is a non-interactive version of the multiparty secure computation, which has been intensively studied to examine the communication cost of the secure computation. We consider its quantum counterpart, the private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement of this model. In the PSQM model, k parties P1,…,Pk initially share a common random string (or entangled states in a stronger setting), and they have private classical inputs x1,…,xk. Every Pi generates a quantum message from the private input xi and the shared random string (entangled states), and then sends it to the referee R. Receiving the messages, R computes F(x1,…,xk). Then, R learns nothing except for F(x1,…,xk) as the privacy condition. We obtain the following results for this PSQM model. (1) We demonstrate that the privacy condition inevitably increases the communication cost in the two-party PSQM model as well as in the classical case presented by Applebaum, Holenstein, Mishra, and Shayevitz. In particular, we prove a lower bound (3−o(1))n of the communication complexity in two-party PSQM protocols with a shared random string for random Boolean functions of 2n-bit input, which is larger than the trivial upper bound 2n of the communication complexity without the privacy condition. (2) We demonstrate a factor two gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings by designing a multiparty PSQM protocol with shared entangled states for a total function that extends the two-party equality function. (3) We demonstrate an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings for a two-party partial function.
In the private simultaneous message (PSM) setting, k players obtain inputs xi∈{0,1}n and then each send messages to a referee, who should learn f(x1,...,xk) but no other information about (x1,...,xk). The PSM setting was introduced as a minimal model for secure multiparty computation and has connections to Boolean function complexity. In the quantum setting, PSM has been related to non-local quantum computation (NLQC). The communication and correlation cost of implementing PSM remains poorly understood. Here, we give new upper and lower bounds on the (quantum) PSM model. For lower bounds, we show: 1) Nečiporuk's measure lower bounds the entanglement required for k-player quantum PSM with perfect correctness. This leads to quadratic lower bounds for explicit functions. 2) The rank of the communication matrix of f(x1,x2) lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness. This implies a previously unknown lower bound on classical PSM with imperfect correctness. When allowing quantum communication and shared entanglement, these are the first lower bounds on quantum PSM that make use of the privacy condition. For upper bounds, we show: 1) Letting s be the size of a quantum circuit computing f, df be the circuit depth, k the number of players, n the number of bits received by each player, and ε a correctness parameter, we obtain PSMk∗(f)≤(kn+s)⋅logO(df)(s/ε). 2) The square of the Fourier 1 norm of f, ∥f^∥12, upper bounds the classical PSM complexity, PSM(f)≤O(∥f^∥12). In proving the first upper bound, we generalize existing T-depth based techniques for NLQC from 2 to k≥2 parties, and consider cases where the Clifford layers are restricted to having small light cones.
Abstract Private Simultaneous Messages (PSM) model is a minimal model for secure multiparty computation. Feige, Kilian, and Naor (STOC 1994) and Ishai (Cryptology and Information Security Series 2013) constructed PSM protocols based on quadratic residues. In this paper, we define QR-PSM protocols as a generalization of these protocols. A QR-PSM protocol is a PSM protocol whose decoding function outputs the quadratic residuosity modulo p of what is computed from messages. We design a QR-PSM protocol for any symmetric function f:{0,1}n→{0,1} f : { 0 , 1 } n → { 0 , 1 } of communication complexity O(n2) O ( n 2 ) . As far as we know, it is the most efficient PSM protocol for symmetric functions since the previously known best PSM protocol was of O(n2logn) O ( n 2 log n ) (Beimel et al., CRYPTO 2014). We also study the sizes of the underlying finite fields Fp F p in the protocols since the communication complexity of a QR-PSM protocol is proportional to the bit length of the prime p. We show that there is a prime p≤(1+o(1))N222N−2 p ≤ ( 1 + o ( 1 ) ) N 2 2 2 N - 2 such that any length-N pattern of quadratic (non)residues appears modulo p (and hence it can be used for general QR-PSM protocols), which improves the Peralta’s known result (Mathematics of Computation 1992) by a constant factor (1+2)2 ( 1 + 2 ) 2 .
Private simultaneous quantum messages (PSQM) provide a minimal model of noninteractive secure multiparty quantum computation, yet their communication complexity for concrete functions remains poorly understood. We show that familiar total functions already exhibit both genuine quantum advantages and strong structural limitations. For three-party equality on n-bit inputs, which determines whether the players' n-bit strings are identical, we construct an entanglement-assisted protocol with asymptotic communication (1.633…)n qubits, whereas every perfectly correct protocol without prior entanglement requires at least 3n qubits. For three-bit majority, one shared GHZ state and one transmitted qubit per player suffice for perfect correctness and perfect privacy, reducing the communication from the optimal classical cost of six bits to three qubits. Three-bit AND behaves differently. No perfectly correct and perfectly private protocol exists when the players share an arbitrary three-qubit state, apply arbitrary local unitary encodings, and transmit one qubit each. However, increasing the local dimension overcomes this obstruction: one shared three-qutrit GHZ state and one transmitted qutrit per player yield a one-shot protocol with total communication 3log23. Together with the six-bit classical lower bound, this gives a strict quantum communication advantage. More generally, for every k≥3, we construct a perfectly correct and perfectly private one-shot protocol for k-bit AND using one qudit of dimension at most k per player, and hence at most klog2k qubits in total.
Quantum signal processing (QSP) and quantum singular value transformation (QSVT) currently stand as the most efficient techniques for implementing functions of block-encoded matrices, a central task that lies at the heart of most prominent quantum algorithms. However, current QSP approaches face several challenges, such as the restrictions imposed on the family of achievable polynomials and the difficulty of calculating the required phase angles for specific transformations. In this paper, we present a generalized quantum signal processing (GQSP) approach, employing general SU(2) rotations as our signal-processing operators, rather than relying solely on rotations in a single basis. Our approach lifts all practical restrictions on the family of achievable transformations, with the sole remaining condition being that |P|≤1 , a restriction necessary due to the unitary nature of quantum computation. Furthermore, GQSP provides a straightforward recursive formula for determining the rotation angles needed to construct the polynomials in cases where P and Q are known. In cases where only P is known, we provide an efficient optimization algorithm capable of identifying in under a minute of GPU time, a corresponding Q for polynomials of degree on the order of 107 . We further illustrate GQSP simplifies QSP-based strategies for Hamiltonian simulation, offer an optimal solution to the ϵ -approximate fractional query problem that requires O((1/δ)+log(1/ϵ)) queries to perform where O(1/δ) is a proved lower bound, and introduces novel approaches for implementing bosonic operators. Moreover, we propose a novel framework for the implementation of normal matrices, demonstrating its applicability through synthesis of diagonal matrices, as well as the development of a new algorithm for convolution through synthesis of circulant matrices using only O(dlogN+log2N) 1 and 2-qubit gates for a filter of lengths d . Published by the American Physical Society 2024
Quantum Signal Processing (QSP) emerges as a groundbreaking paradigm, exploiting the principles of quantum mechanics to revolutionize the analysis, manipulation, and interpretation of signals. This paper introduces a novel framework for QSP, delineating its theoretical foundations and potential to surpass classical signal processing capabilities. The research delves into the development of quantum algorithms that exhibit superior efficiency in the frequency domain analysis and the processing of temporally entangled signal structures. A pivotal aspect of this work is the introduction of quantum Fourier transforms as a mechanism to achieve exponential speed-ups in signal decomposition. Furthermore, the paper explores the implementation of quantum error correction techniques to enhance the robustness of signal processing in the presence of quantum noise and decoherence. The practicality of QSP is demonstrated through simulated quantum circuits, providing a blueprint for future quantum computing hardware applications. The implications of this research are profound, suggesting a transformative impact on fields ranging from secure communications to biomedical imaging. By harnessing the entanglement and superposition properties inherent to quantum systems, QSP is poised to redefine the limits of what is computationally feasible within information processing.