We introduce InfoCommit, a protocol for polynomial commitment and verification. InfoCommit consists of two phases. An initial commitment phase and an evaluation phase. During the commitment phase, the verifier and the prover engage in a private two-party computation algorithm so that the verifier extracts a private verification key. In the evaluation phase, the verifier is interested in learning the evaluations of the polynomial at several input points. InfoCommit has four main features. Firstly, the verifier is able to detect, with high probability, if the prover has responded with evaluations of the same polynomial that he has initially committed to. Secondly, InfoCommit provides rigorous privacy guarantees for the prover: upon observing the initial commitment and the response provided by the prover to $m$ evaluation requests, the verifier only learns $O(m^2)$ symbols about the coefficients of the polynomial. Thirdly, the verifiability guarantee is unconditional and without the need for a trusted party, while bounded storage is the only assumption underlying the privacy of the algorithm. In particular, both properties hold regardless of the computation power of the two parties. Lastly, InfoCommit is doubly-efficient in the sense that in the evaluation phase, the verifier runs in $O(\sqrt{d})$ and the prover runs in $O(d)$ , where $d-1$ is the degree of the polynomial.We introduce InfoCommit, a protocol for polynomial commitment and verification. InfoCommit consists of two phases. An initial commitment phase and an evaluation phase. During the commitment phase, the verifier and the prover engage in a private two-party computation algorithm so that the verifier extracts a private verification key. In the evaluation phase, the verifier is interested in learning the evaluations of the polynomial at several input points. InfoCommit has four main features. Firstly, the verifier is able to detect, with high probability, if the prover has responded with evaluations of the same polynomial that he has initially committed to. Secondly, InfoCommit provides rigorous privacy guarantees for the prover: upon observing the initial commitment and the response provided by the prover to $m$ evaluation requests, the verifier only learns $O(m^2)$ symbols about the coefficients of the polynomial. Thirdly, the verifiability guarantee is unconditional and without the need for a trusted party, while bounded storage is the only assumption underlying the privacy of the algorithm. In particular, both properties hold regardless of the computation power of the two parties. Lastly, InfoCommit is doubly-efficient in the sense that in the evaluation phase, the verifier runs in $O(\sqrt{d})$ and the prover runs in $O(d)$, where $d-1$ is the degree of the polynomial.

Jan 1, 20202 citations

PHASE OPERATORS

WORLD SCIENTIFIC eBooksJun 1, 20000 citations

Evaluating Energy Differences on a Quantum Computer with Robust Phase Estimation

Antonio Russo, Kenneth Rudinger, Benjamin Morrison +1 more

We adapt the robust phase estimation algorithm to the evaluation of energy differences between two eigenstates using a quantum computer. This approach does not require controlled unitaries between auxiliary and system registers or even a single auxiliary qubit. As a proof of concept, we calculate the energies of the ground state and low-lying electronic excitations of a hydrogen molecule in a minimal basis on a cloud quantum computer. The denominative robustness of our approach is then quantified in terms of a high tolerance to coherent errors in the state preparation and measurement. Conceptually, we note that all quantum phase estimation algorithms ultimately evaluate eigenvalue differences.We adapt the robust phase estimation algorithm to the evaluation of energy differences between two eigenstates using a quantum computer. This approach does not require controlled unitaries between auxiliary and system registers or even a single auxiliary qubit. As a proof of concept, we calculate the energies of the ground state and low-lying electronic excitations of a hydrogen molecule in a minimal basis on a cloud quantum computer. The denominative robustness of our approach is then quantified in terms of a high tolerance to coherent errors in the state preparation and measurement. Conceptually, we note that all quantum phase estimation algorithms ultimately evaluate eigenvalue differences.

arXiv:2007.08697Physical Review LettersMay 24, 202153 citations

Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum ComputerAny AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer

Andris Ambainis, Andrew M. Childs, Ben W. Reichardt +2 more

Consider the problem of evaluating an AND-OR formula on an N-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time $N^{1/2+o(1)}$ . In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.Consider the problem of evaluating an AND-OR formula on an N-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time $N^{1/2+o(1)}$. In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.

SIAM Journal on ComputingJan 1, 2010122 citations

States for Phase Estimation

Joshua Combes, Howard M. Wiseman

Jan 1, 20050 citations

m

evaluation requests, the verifier only learns

O(m^2)

symbols about the coefficients of the polynomial. Thirdly, the verifiability guarantee is unconditional and without the need for a trusted party, while bounded storage is the only assumption underlying the privacy of the algorithm. In particular, both properties hold regardless of the computation power of the two parties. Lastly, InfoCommit is doubly-efficient in the sense that in the evaluation phase, the verifier runs in

O(\sqrt{d})

and the prover runs in

O(d)

, where

d-1

is the degree of the polynomial.

Any AND-OR Formula of Size N Can Be Evaluated in Time

N^{1/2+o(1)}

on a Quantum Computer

Consider the problem of evaluating an AND-OR formula on an N-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time

N^{1/2+o(1)}

. In particular, approximately balanced formulas can be evaluated in

O(\sqrt{N})

queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.