We propose an efficiently measurable lower bound on quantum process fidelity of N-qubit controlled-Z gates [arXiv:1306.1141]. 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 of a three-qubit linear optical quantum Toffoli gate. We also demonstrate the entangling capability of the gate by preparing GHZ-type three-qubit entangled states from input product states.