  We propose an efficiently measurable lower bound on quantum process fidelity
of N-qubit controlled-Z gates. This bound is determined by average output state
fidelities for N partially conjugate product bases. A distinct advantage of our
approach is that only fidelities with product states need to be measured while
keeping the total number of measurements much smaller than what is necessary
for full quantum process tomography. As an application, we use this method to
experimentally estimate quantum process fidelity F of a three-qubit linear
optical quantum Toffoli gate and we find that F>=0.83. We also demonstrate the
entangling capability of the gate by preparing GHZ-type three-qubit entangled
states from input product states.
